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(\ while (x!=flag) {

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

_____________________________; //s结点的后继结点是头结点的后继结点 _____________________________; //头结点的后继结点的前驱结点是s结点 _____________________________; //头结点的后继结点是S结点 scanf(\ } }

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

DLNode *s,*r=H; //s指向待插入的结点，r为尾指针指向尾结点 ElemType x; //待插入的数据元素值x printf(\请输入数据以-1为结束:\\n\ scanf(\

while (x!=flag) {

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

_____________________________; //s结点的后继结点为尾结点的后继结点 _____________________________; //头结点的前驱结点为s结点 _____________________________; //r结点的后继结点为s结点 _____________________________; //尾指针指向新插入进来的s结点 scanf(\ } }

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

DLinkList p;//遍历是将双向循环链表中的元素都调用一次。 _____________________________; //p指向头结点的后继结点 while (p!=H) //当p没有回到头结点 {

printf(\输出p结点的值 _____________________________; //p指针后移 }

printf(\}

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

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

_____________________________; //p指向头结点的前驱an结点 while (p!=H) //当p没有回到头结点 {

printf(\输出p结点的值 _____________________________; //p指针前移 }

printf(\}

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(\ printf(\ 双 向 循 环 链 表 常 用 算 法\\n\

printf(\

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

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

printf(\、创建双向循环链表：\\n\ do {

fflush(stdin);

printf(\请选择头插法（T）还是尾插法（W）： \ scanf(\

}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(\、遍历双向双向循环链表：\\n\ /*依次访问双向双向循环链表中所有元素*/ printf(\正向：\ Traverse_DLinkList1 (L);

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

printf(\、双向循环链表长度为：%d\\n\\n\ /*

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

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

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

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

printf(\、双向循环链表的删除操作：\\n\ do {

fflush(stdin);

printf(\请选择按值删除（Z）还是按位序删除（X）： \ scanf(\