数据结构3——链表

文章目录

线性结构离散存储（链表）

线性结构

离散存储（链表）

专业术语 首节点：链表的第一个有效节点尾节点：最后一个有效节点头结点：第一个有效节点之前的节点，头结点并不存放有效数据，主要是为了方便对链表的操作（头结点的数据类型和其他节点的数据类型一致）。头指针：指向头结点的指针变量尾指针：指向尾节点的指针变量 确定一个链表需要几个参数： 一个：头指针。通过头指针可以推断出链表的其他所有信息。 定义： n个节点离散分配彼此通过指针相连每个节点只有一个前驱节点，每个节点只有一个后续节点首节点没有前驱节点，尾节点没有后续节点 链表的分类： 单链表双链表：每一个节点有两个指针域循环链表：能通过任何一个节点找到其他所有节点（尾节点指向头结点）非循环链表 背会这句话：p->pNext； // p所指向结构体变量(节点)中的pNext成员。泛型：利用某种技术达到的效果为：不同的存储方式，执行的操作是一样的。算法（代码在下方） 遍历查找清空销毁求长度排序删除节点（伪算法） 插入节点（伪算法） 代码： # include<stdio.h> # include<malloc.h> # include<stdlib.h> typedef struct Node{ int data; // 数据域 struct Node * pNext; // 指针域 }NODE,*PNODE； // NODE等价于struct Node PNODE等价于struct Node * // 函数声明 PNODE create_list(void); void traverse_list(PNODE pHead); bool is_empty(PNODE pHead); int length_list(PNODE);// 形参的名字写不写无所谓 bool insert_list(PNODE,int,int);// 在pHead所指向链表的第pos个节点的前面插入一个新的节点，该节点的值是val，并且pos的值是从1开始的。 bool delete_list(PNODE,int,int *);// 第三个参数为被删除数据的地址(可有可无) void sort_list(PNODE); int main(viod){ PNODE pHead = null; // 等价于struct Node * pHead = null； pHead = create_list();// 创建一个非循环单链表，并将该链表的头结点的地址赋给pHead； traverse_list(pHead);// 遍历 if(is_empty(pHead)) // 判断链表是否为空 printf("链表为空\n")； else printf("链表不为空\n") int len = length_list(pHead); sort_list(pHead); insert_list(pHead,4,33); return 0; } PNODE create_list(void){ int len;// 用来存放有效节点的个数 int i; int val;// 用来临时存放用户输入的节点的值 PNODE pHead = (PNODE)malloc(sizeof(NODE));// 分配了一个不存放有效数据的头结点 if(NULL == pHead){ printf("分配失败，程序终止")； exit(-1); } PNODE pTail = pHead; // 假定ptail永远指向尾节点 pTail->pNext = null; printf("请输入您要生成的链表节点的个数：len = "); scanf("%d",&len); for(i=0; i<len; ++i){ printf("请输入第%d个节点的值："，i+1); scanf("%d",&val); PNODE pNew = (PNODE)malloc(sizeof(NODE));// 用pNew来造新节点 if(NULL == pHead){ printf("分配失败，程序终止")； exit(-1); } pNew->data = val; pTail->pNext = pNew; pNew->pNext = null; pTail = pNew; } return pHead; } void traverse_list(PNODE pHead){ PNODE p = pHead->pNext; while(NULL != p){ printf("%d",p->data); p = p->pNext; } printf("\n"); return; } bool is_empty(PNODE pHead){ if(NULL == pHead->pNext) return true; else return false; } int length_list(PNODE pHead){ PNODE p = pHead->pNext;// p指向了首节点 int len = 0; while(NULL != p){ ++len; p = p->pNext; } return len; } void sort_list(PNODE pHead){ int i,j,t; int len = length_list(pHead); PNODE p,q; for(i=0,p=pHead->pNext;i<len-1;++i,p=p->pNext){ for(j=i+1,q=p->pNext;j<len;++j,q=q->pNext){ if(p->data > q->data){// 类似于数组中的a[i]>a[j] t = p->data; p->data = q->data; q->data = t; } } } return; } // 在pHead所指向链表的第pos个节点的前面插入一个新的节点，该节点的值是val，并且pos的值是从1开始的。 bool insert_list（PNODE pHead,int pos,int val){ int i = 0; PNODE p = pHead; while(NULL != p && i<pos-1){ p = p->pNext; ++i; } if(i > pos-1 || NULL == p) return false; PNODE pNew = (PNODE)malloc(sizeof(NODE)); if(NULL == pNew){ printf("动态分配内存失败！\n"); exit(-1); } pNew->data = val; PNODE q = p->pNext; p->pNext = pNew; pNew->pNext = q; return ture; } bool delete_list(PNODE pHead,int pos,int * pVal){ int i = 0; PNODE p = pHead; while(NULL != p->pNext && i<pos-1){ p = p->pNext; ++i; } if(i > pos-1 || NULL == p->pNext) return false; PNODE q = p->pNext; *pVal = q->data; p->pNext = p->pNext->pNext; free(q); q = NULL; return ture; }