线性表
定义：线性表是具有相同特性的数据元素的一个有限序列
类型：
1：顺序存储结构
定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构
算法：
#include <stdio.h>
#define LIST_INIT_SIZE 100
#define ERROR 0
#define OK 1
typedef struct{
// 线性表的顺序存储结构
int numbers[LIST_INIT_SIZE];
int length;
}Sqlist;
int ListInsert_Sq(Sqlist * sl,int i,int number);
int ListDelete_Sq(Sqlist * sl,int i);
int main(void){
Sqlist x;
x.numbers[0] = 0;
x.numbers[1] = 1;
x.numbers[2] = 2;
x.length = 3;
printf("数组长度：%d
",x.length);
// 插入线性表 在1的位置插入值5
ListInsert_Sq(&x,1,5);
printf("数组长度：%d
",x.length);
ListDelete_Sq(&x,0);
printf("数组长度：%d
",x.length);
}
// 插入算法
int ListInsert_Sq(Sqlist * sl,int i,int number){
if(i < 0 || i >= sl->length){
return ERROR;
}
int y;
for(y = sl->length;y < i; y--){
sl->numbers[y] = sl->numbers[y-1];
}
sl->numbers[i] = number;
++sl->length;
return OK;
}
// 删除算法
int ListDelete_Sq(Sqlist * sl,int i){
if(i < 0 || i >= sl->length){
return ERROR;
}
int y;
for(y = i;y < sl->length; y++){
sl->numbers[y] = sl->numbers[y+1];
}
--sl->length;
return OK;
}
2:链式存储结构
定义：节点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻
类型：
单链表：节点只有一个指针域的链表，称为单链表。
单链表是由头指针唯一确定，因此单链表可以用头指针的名字来命名
双链表：节点有两个指针域的链表
循环链表：首尾相接的链表
单链表算法：
#include <stdio.h> #include <stdlib.h> #define ERROR 0 #define OK 1 typedef struct Londe{ // 声明节点的类型和指向节点的指针类型 int number; // 节点的数据与 struct Londe *next; // 节点的指针域 }Londe; typedef Londe *LinkList; // LinkList为指向结构体 Londe 的指针类型 // 初始化单链表 int initList_L(LinkList *L); // 清除单链表 int ClearList_L(LinkList L); // 销毁链表 int DestoryList_L(LinkList *L); // 获取链表长度 int GetLength_L(LinkList L); // 通过数据域获取链表索引 int GetDataByI_L(LinkList L,int i); // 删除指定索引 int DeleteIList_L(LinkList *L,int i); // 在指定索引上插入数据 int InsertList_L(LinkList *L,int i,int number); // 遍历链表 int ShowKist_L(LinkList L); int main(void){ // 头指针 LinkList list = NULL; initList_L(&list); //ClearList_L(list); //printf("%p",list); //DestoryList_L(&list); //printf("%p",list); //printf("表长：%d",GetLength_L(list)); //printf("第0个的值%d",GetDataByI_L(list,0)); //ShowKist_L(list); InsertList_L(&list,1,2); InsertList_L(&list,2,3); InsertList_L(&list,3,4); DeleteIList_L(&list,1); ShowKist_L(list); } // 初始化单链表 int initList_L(LinkList *link){ LinkList node = (LinkList)malloc(sizeof(Londe)); if(!node){ return ERROR; } node->number = 1; node->next = NULL; *link = node; return OK; } // 清除单链表 int ClearList_L(LinkList L){ if(!L) { return ERROR; } LinkList per,next; per = L->next; while(per){ next = per->next; free(per); per = next; } L->next = NULL; return OK; } // 销毁单链表 int DestoryList_L(LinkList *L){ LinkList p; while(*L){ p = *L; *L = (*L)->next; free(p); } return OK; } // 求单链表的表长 int GetLength_L(LinkList L){ int length = 0; while(L){ length++; L = L->next; } return length; } // 取第i个元素的值 int GetDataByI_L(LinkList L,int i){ // 判断大小 if(i < 0 || GetLength_L(L) <= i){ return ERROR; } int index = 0; while(L){ if(index == i){ return L->number; } index++; L = L->next; } return ERROR; } // 遍历 int ShowKist_L(LinkList L){ int i = 0; while(L) { printf("第%d个，值%d ",i,L->number); L = L->next; i++; } return 0; } // 在第i个节点插入新节点 // 如果i是0，则插在最后 // 如果i是 GetLength_L(L)，则插在最后面 int InsertList_L(LinkList *L,int i,int number){ if(i < 0 || i > GetLength_L(*L)){ printf("i:%d;length:%d",i,GetLength_L(L)); return ERROR; } int index = 0; LinkList prev = NULL; LinkList next = NULL; LinkList x = *L; while(x){ if(index == i-1){ prev = x; } if(index == i){ next = x; } x = x->next; index++; } LinkList node = (LinkList)malloc(sizeof(Londe)); node->number = number; node->next = NULL; if(prev){ node->next = prev->next; prev->next = node; }else{ *L = node; } return OK; } // 删除第i个节点 int DeleteIList_L(LinkList *L,int i) { if(i < 0 || i > GetLength_L(L)){ return ERROR; } int index = 0; LinkList prev = NULL,now = NULL; LinkList x = *L; while(x){ // 前一个 if(index == i-1){ prev = x; } // 当前个 if(index == i){ now = x; } index++; x = x->next; } prev->next = now->next; if(prev) { prev->next = now->next; }else{ *L = now->next; } free(now); return OK; }