一, 预备知识: typedef
基本使用
- #include <stdio.h>
- typedef int AAA; // 为 int 再重新取一个名字, AAA 就等于 int
- typedef struct Student
- {
- int sid;
- char name[100];
- char sex;
- }ST;
- int main(void)
- {
- int i = 10; // 等价于 AAA = 10;
- struct Student st; // 等价于 ST st;
- struct Student * ps = &st; // 等价于 ST * ps = &st;
- ST st2;
- st2.sid = 10;
- printf("%d \n", st2.sid);
- return 0;
- }
也可以这样使用, 这样更加的方便
- #include <stdio.h>
- typedef struct Student
- {
- int sid;
- char name[100];
- char sex;
- }* PST; // PST 等价于 typedef struct *
- int main(void)
- {
- struct Student st;
- PST ps = &st;
- ps->sid = 99;
- printf("%d\n", ps->sid);
- return 0;
- }
还可以把上面的两个结合起来
- #include <stdio.h>
- typedef struct Student
- {
- int sid;
- char name[100];
- char sex;
- }* PST , STU; // PST 等价于 typedef struct * , STU 代表了 typedef struct
- int main(void)
- {
- STU st; // 等价于 struct Student st
- PST ps = &st;
- ps->sid = 99;
- printf("%d\n", ps->sid);
- return 0;
- }
二, 离散存储 (链表)
定义: n 个节点离散分配, 彼此通过指针相连, 每一个节点只有一个前驱节点和一个后续节点, 首节点没有前驱节点, 尾节点没有后续节点
专业术语:
首节点: 第一个有效节点
尾节点: 最后一个有效节点
头节点: 首节点前面
头指针: 指向头节点的指针变量
尾指针: 指向尾节点的指针变量
注意: 头节点的数据类型和首节点类型一样, 头节点里面没有存放有效数据, 没有实际含义, 为了方便对链表的操作
如果通过希望一个函数来对链表进行处理, 我们至少需要接收链表的那些参数
只需要一个参数: 头指针
因为我们可以通过头指针推算出链表的其他所有参数
每一个链表节点的数据类型如何表示
- #include <stdio.h>
- typedef struct Node
- {
- int data; // 数据域
- struct Node * pNext; // 指针域 指向了和它本身类型一样的另外一个节点
- }NODE , *PNODE;
- // NODE 等价于 struct Node
- // PNODE 等价于 struct Node *
- int main(void)
- {
- return 0;
- }
分类:
单链表
双链表: 每一个节点有两个指针域
循环链表: 能通任何一个节点找到其他所有的节点
非循环链表
算法:
遍历
查找
清空
销毁
求长度
排序
删除节点
插入节点
算法
狭义的算法是与数据的存储方式密切相关
广义的算法与数据的存储方式无关
泛型
利用某种技术达到的效果就是: 不同的存储方式, 执行的操作是一样的
多敲代码, 熟练的掌握, 并进行改进
- #include <stdio.h>
- #include <stdlib.h>
- #include <stdbool.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 pHead);
- bool insert_list(PNODE , int ,int); // 第二个是插入位置, 第三个是插入的值
- bool delete(PNODE , int, int*); // 第二个是删除的位置, 第三个是所删除位置的值
- void sort_list(PNODE pHead);
- int main(void)
- {
- PNODE pHead = NULL; // 等价于 struct Node * pHead = NULL;
- pHead = create_list(); // 创建一个非循环单链表, 并将该链表的头节点地址付给 pHead
- // if(is_empty(pHead))
- // printf("链表为空 \ n");
- // else
- // printf("链表不为空 \ n");
- // printf("链表的长度为 %d\n", length_list(pHead) );
- // sort_list(pHead);
- insert_list(pHead , 4, 99);
- int val;
- if(delete(pHead, 1 , &val))
- {
- printf("删除成功, 你删除的是 %d\n", val);
- }
- else
- {
- printf("删除失败 \ n");
- }
- traverse_list(pHead);
- return 0;
- }
- // 构建一个链表, 并把头节点地址值返回
- PNODE create_list(void)
- {
- int len;
- int i;
- int val; // 用来临时存放用户输入的节点的值
- // 分配了一个不存放数据的头结点
- PNODE pHead = (PNODE)malloc(sizeof(NODE));
- if (pHead == NULL)
- {
- printf("分配失败, 程序终止!\n");
- exit(-1);
- }
- // pTail 始终执行的都是尾结点
- PNODE pTail = pHead;
- pTail->pNext = NULL;
- printf("请输入你需要生成的链表节点的个数:\n");
- scanf("%d" , &len);
- for (i = 0; i <len; ++i)
- {
- printf("请输入第 %d 个节点的值:", i+1);
- scanf("%d" , &val);
- PNODE pNew = (PNODE)malloc(sizeof(NODE));
- if (pNew == NULL)
- {
- printf("分配失败, 程序终止!\n");
- 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(p != NULL){
- printf("%d",p->data );
- p = p->pNext;
- }
- return;
- }
- // 判断链表是否为空
- bool is_empty(PNODE pHead)
- {
- if (pHead->pNext == NULL)
- return true;
- else
- return false;
- }
- // 链表的长度
- int length_list(PNODE pHead)
- {
- // 自定义一个指针用于计算链表的长度
- PNODE p = pHead->pNext;
- int len = 0;
- while(NULL != p)
- {
- ++len;
- p = p->pNext;
- }
- return len;
- }
- // 进行排序
- void sort_list(PNODE pHead)
- {
- // 这里和数组的排序差不多, 思想是一样的
- int i , j , t;
- PNODE p , q;
- int len = length_list(pHead);
- 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)
- {
- 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 true;
- }
- // 删除操作
- bool delete(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 结点后面的结点
- p->pNext = p->pNext->pNext;
- free(q);
- q = NULL;
- return true;
- }
来源: https://www.cnblogs.com/mengd/p/11973677.html