3. 線性表
3.1. 順序表
3.1.3. 順序表編程實現
?操作：增刪改查
.h 文件?
#ifndef __SEQLIST_H__ #define __SEQLIST_H__ #define N 10 typedef struct seqlist {int data[N];int last; //代表數組中最后一個有效元素的下標 } seqlist_t;//1.創建一個空的順序表 seqlist_t *CreateEpSeqlist(); //2.向順序表的指定位置插入數據 int InsertIntoSeqlist(seqlist_t *p, int post, int data); //3.遍歷順序表 void ShowSeqlist(seqlist_t *p); //4.判斷順序表是否為滿，滿返回1,未滿返回0 int IsFullSeqlist(seqlist_t *p); //5.判斷順序表是否為空 int IsEpSeqlist(seqlist_t *p); //6.刪除順序表中指定位置的數據 int DeleteIntoSeqlist(seqlist_t *p, int post); //7.清空順序表 (清空：訪問不到，但是內存中還有；銷毀：內存清空) void ClearSeqList(seqlist_t *p); //8.修改指定位置的數據，post為被修改數據位置，data為修改成的數據 int ChangePostSeqList(seqlist_t *p,int post,int data); //9.查找指定數據出現位置,data為被查找的數據，返回下標，未找到返回-1 int SearchDataSeqList(seqlist_t *p,int data); #endif
?1.創建一個空的順序表
#include <stdio.h> #include "seqlist.h" #include <stdlib.h>// 1.創建一個空的順序表 seqlist_t *CreateEpSeqlist() {// 1. 動態申請一塊空間存放順序表seqlist_t *p = NULL;p = (seqlist_t *)malloc(sizeof(seqlist_t));// 2. 檢測空間是否開辟成功if (NULL == p){perror("malloc last!");return NULL;}else{// 空間開辟成功，對last初始化printf("malloc success!\n");p->last = -1;return p;} }
2.向順序表的指定位置插入數據
#include <stdio.h> #include "seqlist.h"// 2.向順序表的指定位置插入數據 int InsertIntoSeqlist(seqlist_t *p, int post, int data) {// post容錯,post范圍，順序表滿了if (post > p->last + 1 || post < 0 || IsFullSeqlist(p)){perror("Insert Failed");return -1;}// 從post開始，到last，中間的元素向后移動一位for (int i = p->last; i >=post; i--){p->data[i+1] = p->data[i];}p->data[post] = data;p->last++;return 0; }
3.遍歷順序表
#include <stdio.h> #include "seqlist.h"//3.遍歷順序表 void ShowSeqlist(seqlist_t *p) {for (int i = 0; i <= p->last; i++)printf("%-4d", p->data[i]);printf("\n"); }
4. 判斷順序表是否為滿
#include <stdio.h> #include "seqlist.h"// 4.判斷順序表是否為滿，滿返回1,未滿返回0 int IsFullSeqlist(seqlist_t *p) {// if (p->last + 1 == N)// return 1;// else// return 0;return p->last +1 == N; }
5. 判斷順序表是否為空
#include <stdio.h> #include "seqlist.h"// 5.判斷順序表是否為空 int IsEpSeqlist(seqlist_t *p) {return p->last == -1; }
?6. 刪除順序表中指定位置的數據
#include <stdio.h> #include "seqlist.h"// 6.刪除順序表中制定位置的數據 int DeleteIntoSeqlist(seqlist_t *p, int post) {// 容錯判斷if (IsEpSeqlist(p) || post < 0 || post > p->last){perror("Delete Failed！");return -1;}// 從下標為post+1 到last的元素向前移動一個單位for (int i = post + 1; i <= p->last; i++)p->data[i - 1] = p->data[i];p->last--;return 0; }
7. 清空順序表
#include <stdio.h> #include "seqlist.h"// 7.清空順序表 (清空：訪問不到，但是內存中還有；銷毀：內存清空) void ClearSeqList(seqlist_t *p) {p->last = -1; }
8. 修改指定位置的數據
#include <stdio.h> #include "seqlist.h"// 8.修改指定位置的數據，post為被修改數據位置，data為修改成的數據 int ChangePostSeqList(seqlist_t *p, int post, int data) {// 容錯判斷if (post < 0 || post > p->last || IsEpSeqlist(p)){perror("Change Failed！");return -1;}// 修改指定位置的數據p->data[post] = data;return 0; }
9. 查找指定數據出現位置
#include <stdio.h> #include "seqlist.h"// 9.查找制定數據出現位置,data為被查找的數據，返回下標，未找到返回-1 int SearchDataSeqList(seqlist_t *p, int data) {for (int i = 0; i <= p->last; i++)if (p->data[i] == data)return i;return -1; }
?main.c
#include <stdio.h> #include "seqlist.h" #include <stdlib.h>int main(int argc, char const *argv[]) {// 創建空順序表seqlist_t *p = NULL;p = CreateEpSeqlist();// 插入數據InsertIntoSeqlist(p, 0, 1);InsertIntoSeqlist(p, 1, 2);InsertIntoSeqlist(p, 2, 3);InsertIntoSeqlist(p, 3, 4);InsertIntoSeqlist(p, 4, 5);// 遍歷順序表ShowSeqlist(p);// 刪除指定位置的數據DeleteIntoSeqlist(p, 2);ShowSeqlist(p);// 修改指定位置的數據ChangePostSeqList(p, 1, 999);ShowSeqlist(p);// 查找指定數據的位置printf("post = %d\n", SearchDataSeqList(p, 4));// 清空順序表ClearSeqList(p);printf("%d\n",IsEpSeqlist(p));// 釋放空間free(p);return 0; }
3.2. 鏈表 Link
? ? ? ? 鏈表又叫單鏈表，鏈式存儲結構，用于存儲邏輯關系為 “ 一對一 ” 的數據。每個元素配有指針域，存儲和訪問時通過指針域指向下一個節點的地址。
3.2.1. 鏈表的特性
邏輯結構：線性結構
存儲結構：鏈式存儲
特點：內存可以不連續
解決問題：長度固定，插入和刪除操作繁瑣
操作：增刪改查
struct node_t
{int data; // 數據域struct node_t next; // 指針域，存放下一個節點的地址
}；3.2.2. 單向鏈表
1）有頭單向鏈表
? ? ? ? 第一位數據域無效，無法存儲數據
2）無頭單向鏈表
? ? ? ? 第一位數據域有效
?單向鏈表的基本操作
?1. 定義結構體數組，作為鏈表的一個節點
typedef struct Link_list {int data;struct Link_list *next; }link_node_t, *link_list_t;
2. 定義鏈表節點
link_node_t A = {'a', NULL};link_node_t B = {'b', NULL};link_node_t C = {'c', NULL};link_node_t D = {'d', NULL};
3. 定義頭指針
? ? ? ? 無頭
link_list_t h = &A;????????有頭? ? ? ? ? ? 定義頭節點，讓頭指針指向頭節點
link_node_t S = {'\0', &A}; link_list_t h = &S;
4. 遍歷鏈表
? ? ? ? 無頭
while (h != NULL){printf("%-4c", h->data);h = h->next;}printf("\n");? ? ? ? 有頭
按照有頭節點方式遍歷
while (h->next != NULL) {h = h->next;printf("%-4c", h->data); }按照無頭節點方式遍歷
h = h->next; while(h != NULL) {printf("%-4c", h->data);h = h->next; }
?有頭單向鏈表的函數操作
頭文件 .h?
#ifndef __LINKLIST_H__ #define __LINKLIST_H__typedef int datatype; typedef struct node_t {datatype data; // 數據域struct node_t *next; // 指針域,指向自身結構體的指針 } link_node_t, *link_list_t;// 1.創建一個空的有頭單向鏈表 link_list_t createEmptyLinkList(); // 2.鏈表指定位置插入數據 int insertIntoPostLinkList(link_node_t *p, int post, datatype data); // 3.計算鏈表的長度。 int lengthLinkList(link_node_t *p); // 4.遍歷鏈表 void showLinkList(link_node_t *p); // 5.鏈表指定位置刪除數據 int deletePostLinkList(link_node_t *p, int post); // 6.判斷鏈表是否為空 int isEmptyLinkList(link_node_t *p); // 7.清空單向鏈表 void clearLinkList(link_node_t *p); // 8.修改指定位置的數據 post 被修改的位置 data修改成的數據 int changePostLinkList(link_node_t *p, int post, datatype data); // 9.查找指定數據出現的位置 data被查找的數據 //search 查找 int searchDataLinkList(link_node_t *p, datatype data); // 10.刪除單向鏈表中出現的指定數據,data代表將單向鏈表中出現的所有data數據刪除 int deleteDataLinkList(link_node_t *p, datatype data); // 11.轉置鏈表 // 解題思想： //(1) 將頭節點與當前鏈表斷開，斷開前保存下頭節點的下一個節點， // 保證后面鏈表能找得到，定義一個q保存頭節點的下一個節點， // 斷開后前面相當于一個空的鏈表，后面是一個無頭的單向鏈表 //(2) 遍歷無頭鏈表的所有節點， // 將每一個節點當做新節點插入空鏈表頭節點的下一個節點 // (每次插入的頭節點的下一個節點位置) void reverseLinkList(link_node_t *p); #endif
1. 創建一個空的有頭單項鏈表
link_node_t *createEmptyLinkList() {link_list_t h = (link_list_t)malloc(sizeof(link_node_t));// 容錯判斷if (h == NULL){perror("空間開辟失敗\n");return NULL;}// 頭節點初始化h->next=NULL;return h; }
2. 鏈表指定位置插入節點
int insertIntoPostLinkList(link_node_t *p, int post, datatype data) {link_list_t pnew = NULL; // 指向新節點// 容錯判斷if(post > lengthLinkList(p) || post < 0){perror("post 范圍錯誤");return -1;}// 創建新節點并初始化pnew = (link_list_t)malloc(sizeof(link_node_t));pnew->data = data;pnew ->next = NULL;// 移動頭指針，指向插入位置的前一個節點for(int i = 0; i < post; i++){p = p->next;}// 鏈接插入節點pnew->next = p->next;p ->next = pnew;return 0; }
3. 計算鏈表長度
int lengthLinkList(link_node_t *p) {int len = 0;while (p->next != NULL){p = p->next;len++;}return len; }
4. 遍歷鏈表
void showLinkList(link_node_t *p) {while (p->next != NULL){p = p->next;printf("%-4d", p->data);} }
；與wp_footer()；的區別的關系)
