链表结构体嵌套结构体 静态链表 动态链表/单向链表/传统链表 非传统链表 双向链表 循环链表 一、链表热身(结构体套结构体)1 结构体中套一个结构体 //数据类型本质:固定大小内存块的别名 //在自己类型大小 还没有确定的情况下 引用自己类型的元素 是不正确的 typedef struct student { char name[64]; int id; }student; typedef struct teacher { char name[64]; int id; char *p; student s1; student *s2; //struct teacher t1;//err!! struct teacher *t1; }teacher; void main() { teacher t1, t2; system('pause'); } 二、静态链表静态链表是用结构体数组实现的(个数固定,在栈上分配内存),这种链表在初始时必须分配足够的空间, 初始长度是固定的,也就是说内存空间大小是静态的。 注意静态链表与顺序表的区别:静态链表是用数组实现*next,有本质的区别。
typedef struct Teacher { int data; struct Teacher *next; }Teacher; //创建一个链表,并返回一个头结点的地址 Teacher* createList() { Teacher t1, t2, t3; Teacher *p = NULL; t1.data = 100; t2.data = 200; t3.data = 300; t1.next = &t2; t2.next = &t3; t3.next = NULL; //遍历 p = &t1; while (p) { printf('data:%d', p->data); p = p->next; } return &t1; } void main() { Teacher *head = createList(); system('pause'); } 三、动态链表(单向链表)动态链表是用申请内存函数(C是malloc,C++是new)动态申请内存的,所以在链表的长度上没有限制。 测试框架: void main() { int ret = 0; SLIST *pHead = NULL; pHead = SList_Create(); ret = SList_Print(pHead); ret=SList_Insert(pHead, 20, 19); ret = SList_Print(pHead); ret = SList_Delete(pHead, 20); ret = SList_Print(pHead); ret = SList_Reverse(pHead); ret = SList_Print(pHead); ret = SList_Destory(pHead); system('pause'); } 1、创建+遍历: 内存四区图:(重点)
步骤图: typedef struct Node { int data; struct Node *next; }SLIST; //创建链表 SLIST* SList_Create() { SLIST *pHead, *pCur, *pM; int data; //1、创建一个头结点,并初始化 pHead = (SLIST*)malloc(sizeof(SLIST)); pHead->data = 0; pHead->next = NULL; //2、pCur初始化 pCur = pHead; printf('please input your data:'); scanf('%d', &data); while (data != -1) { //3、申请一块新的内存,malloc新结点 pM = (SLIST*)malloc(sizeof(SLIST)); pM->data = data; pM->next = NULL; //4、新结点入链表 pCur->next = pM; //5、新结点变成当前结点 pCur = pM; printf('please input your data:'); scanf('%d', &data); } return pHead; } //遍历 int SList_Print(SLIST *pHead) { SLIST *p = NULL; if (pHead == NULL) { return -1; } p = pHead->next; printf('\nBegin\t'); while (p) { printf('%d\t', p->data); p = p->next; } printf('\tEnd'); return 0; } void main() { int ret = 0; SLIST *pHead = NULL; pHead = SList_Create(); ret = SList_Print(pHead); system('pause'); } 2、插入:
int SList_Insert(SLIST *pHead, int x, int y) { SLIST *pPre, *pCur, *pM; //1 pM = (SLIST*)malloc(sizeof(SLIST)); pM->data = y; pM->next = NULL; //2 pPre = pHead; pCur = pPre->next; //3 while (pCur) { if (pCur->data == x) { break; } pPre = pCur; pCur = pCur->next; } //4 pM->next = pCur; pPre->next = pM; return 0; } 3、删除 int SList_Delete(SLIST *pHead, int x) { SLIST *pPre, *pCur; //1 pPre = pHead; pCur = pPre->next; //2 while (pCur) { if (pCur->data == x) { break; } pPre = pCur; pCur = pCur->next; } //3、 pPre->next=pCur->next; //4、释放删除对象的内存 free(pCur); return 0; } 4、销毁: int SList_Destory(SLIST *pHead) { SLIST *p, *tmp; p = pHead; if (p == NULL) { return -1; } while (p != NULL) { tmp = p->next; free(p); p = tmp; } return 0; } 5、逆置 纠正:第三步应该是:pHead->next->next=NULL,pHead->next=p;
int SList_Reverse(SLIST *pHead) { //1 SLIST *p = NULL; SLIST *q = NULL; SLIST *t = NULL; if (pHead == NULL || pHead->next == NULL || pHead->next->next == NULL) { return -1; } p = pHead->next; q = pHead->next->next; //2/逆置 while (q) { t = q->next;//逆置前先缓存q->next q->next = p;//逆置 p = q; q = t; } //3/处理头结点 pHead->next->next = NULL;//注意这里一定是先这一步 pHead->next = p; return 0; } 四、链表技术推演
|
|