14°

数据结构入门-离散存储(链表)

#### 离散存储(链表) #### 一、预备知识:typedef 基本使用 ```c #include 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; } ``` 也可以这样使用,这样更加的方便 ```c #include 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; } ``` 还可以把上面的两个结合起来 ```c #include 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个节点离散分配,彼此通过指针相连,每一个节点只有一个前驱节点和一个后续节点,首节点没有前驱节点,尾节点没有后续节点 专业术语: 1. 首节点:第一个有效节点 2. 尾节点:最后一个有效节点 3. 头节点:首节点前面 4. 头指针:指向头节点的指针变量 5. 尾指针:指向尾节点的指针变量 **注意:头节点的数据类型和首节点类型一样,头节点里面没有存放有效数据,没有实际含义,为了方便对链表的操作** #### 如果通过希望一个函数来对链表进行处理,我们至少需要接收链表的那些参数 **只需要一个参数:头指针** 因为我们可以通过头指针推算出链表的其他所有参数 #### 每一个链表节点的数据类型如何表示 ```c #include typedef struct Node { int data; // 数据域 struct Node * pNext; // 指针域 指向了和它本身类型一样的另外一个节点 }NODE , *PNODE; // NODE 等价于struct Node // PNODE 等价于struct Node * int main(void) { return 0; } ``` 分类: 1. 单链表 2. 双链表:每一个节点有两个指针域 3. 循环链表:能通任何一个节点找到其他所有的节点 4. 非循环链表 算法: 1. 遍历 2. 查找 3. 清空 4. 销毁 5. 求长度 6. 排序 7. 删除节点 8. 插入节点 #### 算法 狭义的算法是与数据的存储方式密切相关 广义的算法与数据的存储方式无关 #### 泛型 利用某种技术达到的效果就是:**不同的存储方式,执行的操作是一样的** 多敲代码,熟练的掌握,并进行改进 ```c #include #include #include 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/11973649.html

全部评论: 0

    我有话说: