S 实验二 双向循环链表

#include

#include

typedef int ElemType; /* 定义链表数据元素类型ElemType，int类型 */

#define TRUE 1

#define FALSE 0

#define flag -1

typedef struct node { //双向循环链表的结点类型

ElemType data; //数据域

struct node *prior, *next; //指针域

} DLNode, *DLinkList; // DLNode是此结构体的类型名，而*DLinkList是结构体指针的类型名

DLinkList Init_DLinkList()/* 初始化双向循环链表，建立一个空的双向循环链表 */ {

DLinkList H=(DLinkList)malloc(sizeof(DLNode)); //为头结点分配内存

_____________________________; //设置头结点前驱结点为它自己

_____________________________; //设置头结点后继结点为它自己

return H;

}

void Create_DLinkList1(DLinkList H ) /*头插法建立双向循环链表*/

{

DLNode *s; //指向双向循环链表结点的指针s

ElemType x; //待插入的数据元素值x

printf("请输入双向循环链表数据元素，以-1为结束:\n");

scanf("%d",&x);

while (x!=flag)

{

s=(DLinkList)malloc(sizeof(DLNode)); //为s指向的结点分配内存

s->data=x; //设置s指向的结点的数据域为x

_____________________________; //s结点的前驱结点是头结点

_____________________________; //s结点的后继结点是头结点的后继结点 _____________________________; //头结点的后继结点的前驱结点是s结点 _____________________________; //头结点的后继结点是S结点

scanf("%d",&x);

}

}

void Create_DLinkList2( DLinkList H) /*尾插法建立双向循环链表*/

{

DLNode *s,*r=H; //s指向待插入的结点，r为尾指针指向尾结点

ElemType x; //待插入的数据元素值x

printf("请输入数据以-1为结束:\n");

scanf("%d",&x);

while (x!=flag)

{

s=(DLinkList)malloc(sizeof(DLNode)); //为s指向的结点分配内存 s->data=x; //设置s指向的结点的数据域为x

_____________________________; //s结果的前驱是尾结点

_____________________________; //s结点的后继结点为尾结点的后继结点 _____________________________; //头结点的前驱结点为s结点 _____________________________; //r结点的后继结点为s结点

_____________________________; //尾指针指向新插入进来的s结点 scanf("%d",&x);

}

}

void Traverse_DLinkList1(DLinkList H)/* 正向遍历双向循环链表 */

{

DLinkList p;//遍历是将双向循环链表中的元素都调用一次。

_____________________________; //p指向头结点的后继结点

while (p!=H) //当p没有回到头结点

{

printf("%d ",_____________________________); //输出p结点的值 _____________________________; //p指针后移

}

printf("\n");

}

void Traverse_DLinkList2(DLinkList H)/* 逆向遍历双向循环链表 */

{

DLinkList p;//遍历是将双向循环链表中的元素都调用一次。

_____________________________; //p指向头结点的前驱an结点

while (p!=H) //当p没有回到头结点

{

printf("%d ",_____________________________); //输出p结点的值 _____________________________; //p指针前移

}

printf("\n");

}

int Length_DLinkList (DLinkList H) /*求双向循环链表长度*/

{

DLinkList p=H; //p指向头结点

int j=0; //结点计数器j归零

while (_____________________________) //当p没有回到头结点

{

_____________________________; //计数器+1

p=p->next; //指针后移

}

return j;

}

DLinkList Get_DLinkList (DLinkList H, int k) /*按位序查找结点指针*/

{ }

ElemType Get_DLinkList1 (DLinkList H, int k) /*按位序查找元素值*/

{ }

DLinkList Get_DLinkList2 (DLinkList H, ElemType x) /*按值查找结点指针*/

{ }

int Get_DLinkList3 (DLinkList H, ElemType x) /*按值查找结点位序*/

{ }

int Insert_DLinkList1(DLinkList H, int i, ElemType x) /*在链表中第i个位置插入元素*/ {}

int Del_DLinkList1 (DLinkList H,ElemType x) /*按值删除节点*/

{}

int Del_DLinkList2 (DLinkList H, int i) /*按位序删除节点*/

{}

ElemType Min_DLinkList (DLinkList H) /*查找双向循环链表最小值*/

{ }

void Reverse_DLinkList(DLinkList H) /*逆置双向循环链表*/

{}

void Pur_DLinkList (DLinkList H) /*删除重复元素*/

{}

int FindLast_DLinkList (DLinkList H,int k) /*查找双向循环链表倒数第k个元素值*/ { }

int main()

{

int i,j;

char ch;

ElemType e;

DLinkList L;

ElemType x;

printf("**************************************************\n");

printf(" 双 向 循 环 链 表 常 用 算 法\n");

printf("**************************************************\n\n");

printf("1、初始化双向循环链表:设置其为空表\n");

L=Init_DLinkList();

if(L) printf("双向循环链表初始化成功……\n\n");

printf("2、创建双向循环链表：\n");

do

{

fflush(stdin);

printf("请选择头插法（T）还是尾插法（W）： ");

scanf("%c",&ch);

}while(ch!='T' && ch!='t' && ch!='W' && ch!='w');

if(ch=='T' || ch=='t') Create_DLinkList1(L);

else Create_DLinkList2(L);

printf("双向循环链表创建成功……\n\n");

printf("3、遍历双向双向循环链表：\n"); /*依次访问双向双向循环链表中所有元素*/ printf("正向："); Traverse_DLinkList1 (L);

printf("逆向："); Traverse_DLinkList2 (L); printf("\n");

printf("4、双向循环链表长度为：%d\n\n",Length_DLinkList(L));

/*

printf("5、双向循环链表的插入操作：\n");

printf("请输入待插入的数据及其位序(location,data)：");

scanf("%d,%d",&i,&e);

if(Insert_DLinkList1(L,i,e)) printf("插入操作执行成功……\n操作结果：\n");

printf("正向："); Traverse_DLinkList1 (L);

printf("逆向："); Traverse_DLinkList2 (L); printf("\n");

printf("6、双向循环链表的删除操作：\n");

do

{

fflush(stdin);

printf("请选择按值删除（Z）还是按位序删除（X）： ");

scanf("%c",&ch);

}while(ch!='Z' && ch!='z' && ch!='X' && ch!='x');

if(ch=='Z' || ch=='z')

{ printf("请输入待删除的数据元素值：");

scanf("%d",&x);

if(Del_DLinkList1(L,x)) printf("删除操作执行成功……\n操作结果：\n"); else printf("删除操作未执行成功……\n操作结果：\n");

}

if(ch=='X' || ch=='x')

{ printf("请输入待删除的数据的位序：");

scanf("%d",&e);

if(Del_DLinkList2(L,e)) printf("删除操作执行成功……\n操作结果：\n"); else printf("删除操作未执行成功……\n操作结果：\n");

}

printf("正向："); Traverse_DLinkList1 (L);

printf("逆向："); Traverse_DLinkList2 (L); printf("\n");

printf("7、双向循环链表的查找操作：\n");

do

{

fflush(stdin);

printf("请选择按值查找（Z）还是按位序查找（X）： ");

scanf("%c",&ch);

}while(ch!='Z' && ch!='z' && ch!='X' && ch!='x');

if(ch=='Z' || ch=='z')

{ printf("请输入待查找的数据元素值：");

scanf("%d",&x);

if(Get_DLinkList3(L,x)) printf("待查找的值为%d数据元素为：%d\n\n",x,Get_DLinkList3(L,x));

else printf("待查找的值为%d数据元素不存在\n\n",x);

}

if(ch=='X' || ch=='x')

{ do

{ printf("请输入待查找的数据元素的位序（1~%d）：", Length_DLinkList(L)); scanf("%d",&i);

} while(i Length_DLinkList(L));

x=Get_DLinkList1(L,i);

printf("待查找的位序为%d数据元素值为：%d \n\n",i,x);

}

printf("8、双向循环链表的最小值：");

printf("%d\n\n", Min_DLinkList(L));

printf("9、逆置双向循环链表：\n");

Reverse_DLinkList(L); 位序的

printf("正向："); Traverse_DLinkList1 (L);

printf("逆向："); Traverse_DLinkList2 (L); printf("\n");

printf("10、删除重复元素：\n");

Pur_DLinkList(L);

printf("正向："); Traverse_DLinkList1 (L);

printf("逆向："); Traverse_DLinkList2 (L); printf("\n");

printf("11、查找倒数元素\n请输入倒数的位序："); scanf("%d",&i);

j=FindLast_DLinkList (L,i);

*/

return 0;

}