不带头节点的循环双链表

1.创建一个双链表的类型

typedef struct DLNode { int data; struct DLNode* prior, * next;//里面有两个指针，一个前驱指针，一个后驱指针 } DLNode, * DLinkList;//重新定义一个名字，DLNode是节点名字，DLinkList是双链条的名字，也是个指针

2.用创建好的结构体创建一个变量，进行初始化

int InitDLinkList(DLinkList*L) { (*L) = NULL;//把表头置为空 return 0; }

3.判断表是不是空表，因为有两个节点指针，判断节点指针是不是都为空即可

int Is_empty(DLinkList*L) { return((*L)->next == NULL) && ((*L)->prior == NULL);//只要两个节点都指向空说明这个链表没有数据 }

4.给定一个位序进行插入，因为不带头节点所以考虑的事情相对多，要考虑第一个元素可最后一个元素

int insertLocate(DLinkList* L, int i, int elem)//在位序为i处插入一个elem 的元素 { if (i < 0) { return 1; } if (i == 1) { DLNode* s = (DLNode*)malloc(sizeof(DLNode)); if (s == NULL) { return 1; } s->data = elem; s->next = NULL; s->prior = NULL; (*L) = s; return 0; } int j = 1; DLNode* p = (*L);//将第一个元素付给p节点，就一个节点这个节点就是p while (p != NULL && j < i - 1) { p = p->next; j++; } if (p == NULL) { return 1;//i的值不合法 } DLNode* q = (DLNode*)malloc(sizeof(DLNode)); if (q == NULL) { return 1; } q->data = elem; q->next = p->next; if(p->next!=NULL)//如果等于就只需要链接三条线因为最后一个元素没有前驱指针 p->next->prior = q; p->next = q; q->prior = p; return 0; }

5.给定一个节点进行插入操作

int InsertDLNode(DLinkList* L, DLNode* p,DLNode*s, int elem)//在指定的节点p插入一个数据元素为elem的数据 { if (p == NULL) { return 1; } s->next = p->next;//插入到p节点的后面，然后交换p指针和q指针的值 if(p->next!=NULL) p->next->prior = s; p->next = s; s->prior = p; s->data = p->data; p->data = elem; return 0; }

6.给定一个值，查找这个值的位序

int GetLocate(DLinkList* L, int elem)//查找elem的位序 { DLNode* p = (*L); int count = 0; while (p) { count++; if (p->data == elem) { return count;//返回位序 } p = p->next; } return -1;//找不到返回-1

7.给定一个值，删除第一个相同的值

nt DeleteElem(DLinkList* L, int elem) { if ((*L)->data == elem) { DLNode* p = (*L)->next; (*L)->next->prior = (*L)->prior; free(*L); (*L) = p; } int pos=GetLocate(L, elem);//pos=位序 int j = 1; DLNode* p = (*L); while (p != NULL && j < pos - 1) { p = p->next; j++; } if (p == NULL) { return 0; } DLNode* ptr = p->next; p->next = ptr->next; if (ptr->next != NULL) ptr->next->prior = p; free(ptr); }

8.打印整个链表的数据

void Display(DLinkList* L) { DLNode* p = (*L); while (p!=NULL)//如果p等于NULL说明这个时候就是错误的，不会进入循环里面 { printf("%d-> ", p->data); p = p->next; } printf("NULL\n"); }

9.头插法建立双链表，头插法很重要，链表的逆置需要用到头插法

int HeadInsert(DLinkList* L)//头插法建立单链表 { int x = 0; scanf("%d", &x); DLNode* s = (DLNode*)malloc(sizeof(DLNode)); if (s == NULL) { return 1; } s->data = x; s->next = NULL; s->prior = NULL;//头插法建立双链表的时候先整一个头节点，逻辑上的头节点 (*L) = s; scanf("%d", &x); while (x)//x为零就结束建立 { DLNode* s = (DLNode*)malloc(sizeof(DLNode)); if (s == NULL) { return 1; } s->next = (*L); (*L)->prior = s; s->data = x; (*L) = s; scanf("%d", &x); } return 0; }

10.尾插法建立单链表

int TailInsert(DLinkList* L) { int x = 0; scanf("%d", &x); DLNode* s = (DLNode*)malloc(sizeof(DLNode)); if (s == NULL) { return 1; } s->data = x; s->next = NULL; s->prior = NULL; (*L) = s; //(*L)->next = NULL; scanf("%d", &x); DLNode* tail = (*L);//把头节点赋值个头指针 while (x) { DLNode* s = (DLNode*)malloc(sizeof(DLNode)); if (s == NULL) { return 1; } s->data = x; tail->next = s->next; s->prior = tail; tail->next = s; tail = s; scanf("%d", &x); } tail->next = NULL;//最后要把尾指针置为NULL return 0; }

11.总体代码

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> typedef struct DLNode { int data; struct DLNode* prior, * next;//里面有两个指针，一个前驱指针，一个后驱指针 } DLNode, * DLinkList;//重新定义一个名字，DLNode是节点名字，DLinkList是双链条的名字，也是个指针 int InitDLinkList(DLinkList*L) { (*L) = NULL;//把表头置为空 return 0; } int Is_empty(DLinkList*L) { return((*L)->next == NULL) && ((*L)->prior == NULL);//只要两个节点都指向空说明这个链表没有数据 } int InsertDLNode(DLinkList* L, DLNode* p,DLNode*s, int elem)//在指定的节点p插入一个数据元素为elem的数据 { if (p == NULL) { return 1; } s->next = p->next;//插入到p节点的后面，然后交换p指针和q指针的值 if(p->next!=NULL) p->next->prior = s; p->next = s; s->prior = p; s->data = p->data; p->data = elem; return 0; } int insertLocate(DLinkList* L, int i, int elem)//在位序为i处插入一个elem 的元素 { if (i < 0) { return 1; } if (i == 1) { DLNode* s = (DLNode*)malloc(sizeof(DLNode)); if (s == NULL) { return 1; } s->data = elem; s->next = NULL; s->prior = NULL; (*L) = s; return 0; } int j = 1; DLNode* p = (*L);//将第一个元素付给p节点，就一个节点这个节点就是p while (p != NULL && j < i - 1) { p = p->next; j++; } if (p == NULL) { return 1;//i的值不合法 } DLNode* q = (DLNode*)malloc(sizeof(DLNode)); if (q == NULL) { return 1; } q->data = elem; q->next = p->next; if(p->next!=NULL)//如果等于就只需要链接三条线因为最后一个元素没有前驱指针 p->next->prior = q; p->next = q; q->prior = p; return 0; } int GetLocate(DLinkList* L, int elem)//查找elem的位序 { DLNode* p = (*L); int count = 0; while (p) { count++; if (p->data == elem) { return count;//返回位序 } p = p->next; } return -1;//找不到返回-1 } int DeleteElem(DLinkList* L, int elem) { if ((*L)->data == elem) { DLNode* p = (*L)->next; (*L)->next->prior = (*L)->prior; free(*L); (*L) = p; } int pos=GetLocate(L, elem);//pos=位序 int j = 1; DLNode* p = (*L); while (p != NULL && j < pos - 1) { p = p->next; j++; } if (p == NULL) { return 0; } DLNode* ptr = p->next; p->next = ptr->next; if (ptr->next != NULL) ptr->next->prior = p; free(ptr); } void Display(DLinkList* L) { DLNode* p = (*L); while (p!=NULL)//如果p等于NULL说明这个时候就是错误的，不会进入循环里面 { printf("%d-> ", p->data); p = p->next; } printf("NULL\n"); } int HeadInsert(DLinkList* L)//头插法建立单链表 { int x = 0; scanf("%d", &x); DLNode* s = (DLNode*)malloc(sizeof(DLNode)); if (s == NULL) { return 1; } s->data = x; s->next = NULL; s->prior = NULL;//头插法建立双链表的时候先整一个头节点，逻辑上的头节点 (*L) = s; scanf("%d", &x); while (x)//x为零就结束建立 { DLNode* s = (DLNode*)malloc(sizeof(DLNode)); if (s == NULL) { return 1; } s->next = (*L); (*L)->prior = s; s->data = x; (*L) = s; scanf("%d", &x); } return 0; } int TailInsert(DLinkList* L) { int x = 0; scanf("%d", &x); DLNode* s = (DLNode*)malloc(sizeof(DLNode)); if (s == NULL) { return 1; } s->data = x; s->next = NULL; s->prior = NULL; (*L) = s; //(*L)->next = NULL; scanf("%d", &x); DLNode* tail = (*L);//把头节点赋值个头指针 while (x) { DLNode* s = (DLNode*)malloc(sizeof(DLNode)); if (s == NULL) { return 1; } s->data = x; tail->next = s->next; s->prior = tail; tail->next = s; tail = s; scanf("%d", &x); } tail->next = NULL;//最后要把尾指针置为NULL return 0; } int main() { DLinkList L; InitDLinkList(&L); /*insertLocate(&L, 1, 2); insertLocate(&L, 2, 3); insertLocate(&L, 3, 4); insertLocate(&L, 4, 5); insertLocate(&L, 5, 6);*/ TailInsert(&L); //insertLocate(&L, 6, 7); //DeleteElem(&L,7); //DeleteElem(&L, 7); int ret=Is_empty(&L); if (ret) { printf("空\n"); } else { printf("非空\n"); } Display(&L); int pos = GetLocate(&L, 6); printf("%d\n",pos);// return 0; }