数据结构大合集02——线性表的相关函数运算算法

注：
本篇文章的概念合集
数据结构的概念大合集02（线性表）

顺序表的结构体

typedef struct
{ElemType data[MaxSize];int length;
} SqList;

顺序表的基本运算的实现

1. 建立顺序表

//建立顺序表
void CreatList(SqList *L,ElemType a[],int n)
{int i = 0,k = 0;L = (SqList *)malloc(sizeof(SqList));while(i<n){L->data[k] = a[i];k++ ;i++;}L->length = k;
}

2. 顺序表的基本运算

2.1 初始化线性表

//初始化线性表
void InitList(SqList *L)
{L = (SqList *)malloc(sizeof(SqList));L ->length = 0;
}

2. 2 销毁顺序表

//销毁顺序表
void DestroyList(SqList *L)
{free(L);
}

2.3 判断顺序表是否为空表

//判断顺序表是否为空表
bool ListEmpty(SqList *L)
{return(L->length == 0);
}

2.4 求顺序表的长度

//求顺序表的长度
int ListLength(SqList *L)
{return(L->length);
}

2.5 输出顺序表

//输出顺序表
void DisList(SqList *L)
{int i;for(i = 0; i < L->length; i++){printf("%d",L->data[i]);printf("\n");}
}

2.6 按序号求顺序表中的元素

//按序号求顺序表中的元素，采用bool性，即可以满足函数所需功能，还能增加复用性
bool GetElem(SqList * L,int i,ElemType *e)
{if(i < 1 || i > L->length) return false;e = L->data[i-1];return true;
}

2.7 按元素值查找

//按元素值查找
int LocateElem(SqList *L,ElemType e)
{int i;while(i < L->length && L->data[i] == e){i++;}if(i >= L->length){return 0;}else{return i+1;}
}

2.8 插入数据元素

//插入数据元素，在i位置插入元素e<==>把i后面的元素后移一个位置
bool ListInsert(SqList * L,int i,ElemType e)
{int j;if(i < 1 || i > L->length+1 || L->length == MaxSize)return false;i--;for(j = L->length; j > i; j--)  //此循环就是为了做到时i后面的元素后移一个位置{L->data[j] = L->data[j-1];};L->data[i] = e;L->length++;return true;
}

2.9 删除数据元素

//删除数据元素
bool ListDelet(SqList *L,int i,ElemType *e){int j;if(i<1 || i > L->length)return false;e = L->data[i];for(j = L->length; j >= i; j--){L->data[j-1] = L->data[j];}L->length--;return true;
}

单链表的结构体

typedef struct LNode{ElemType data;struct Lnode *next;
}LinkNode;

单链表的基本运算的实现

1.建立单链表

1.1头插法

//建立单链表——头插法
void CreatListF (LinkNode *L,ElemType a[],int n){LinkNode *s;L = (LinkNode*)malloc(sizeof(LinkNode));L->next = NULL;for(int i = 0; i < n; i++){s = (LinkNode*)malloc(sizeof(LinkNode));s->data = a[i];s->next = L->next;  //将s的后继结点始终置空，这是为了让尾结点的指针置空L->next = s;    //将头结点的指针始终指向新插入进来的元素}
}

使用头插法后，数组a里面的元素会倒置，比如a[5] = {1,2,3,4,5},头插法后，链表里面的元素是 5,4,3,2,1 ，具体原因可以多体会一下上述代码中的for循环部分。

1.2尾插法

//建立单链表——尾插法
void CreatListR(LinkNode *L,ElemType a[],int n){LinkNode *s,*r;L = (LinkNode*)malloc(sizeof(LinkNode));r = L;for(int i = 0;i < n;i++){s = (LinkNode*)malloc(sizeof(LinkNode));s->data = a[i];r->next = s;    //将r的后继结点指向sr=s;    //将s赋给r，相当于将r后移，这样，结合上行代码，就可以是元素依次插入到头结点后面，且顺序不会倒置}r -> next = NULL;   //经过循环后，r变成尾结点，此行代码，就是为了让尾指针为空
}

与头插法不同，尾插法后得到的元素不会倒置，这都是 LinkNode* r 的功能

2.单链表的基本运算

2.1 初始化单链表

void InitList(LinkNode *L)
{L = (LinkNode*)malloc(sizeof(LinkNode));L->next = NULL;
}

2.2 销毁单链表

//销毁单链表
void DestroyList(LinkNode *L)
{LinkNode *pre = L, *p = L->next;while(p!=NULL){free(pre);pre = p;p = pre->next;}free(pre);
}

2.3 判断单链表是否为空表

//判断单链表是否为空
bool ListEmpty(LinkNode *L)
{return(L->next == NULL);
}

2.4 求单链表的长度

//求链表的长度
int ListLenth(LinkNode *L)
{int n = 0;LinkNode *p;while(p != NULL){n++;p = p->next;}return n;
}

2.5 输出单链表

//输出单链表
void DispList(LinkNode *L)
{LinkNode * p = L->next;while (p != NULL){printf("%d",p->data);p=p->next;}printf("\n");
}

2.6 按序号求单链表的元素

//按序号求单链表中的元素
bool GetElem(LinkNode * L,int i,ElemType *e)
{int j = 0;LinkNode *p = L;if(i <= 0) return false;while(j < i && p != NULL){j++;p = p->next;}if(p == NULL){return false;}else{e = p->data;return true;}
}

2.7 按元素值查找

//按元素值查找
int LocateElem(LinkNode *L,ElemType e){int i = 1;LinkNode *p = L->next;while(p != NULL && p->data != e){p = p->next;i++;}if(p == NULL)return 0;elsereturn i;
}

2.8 插入数据元素

//插入数据元素
bool ListInsert(LinkNode *L,int i,ElemType e){int j = 0;LinkNode *p = L,*s;if(i <= 0) return false;while(j < i-1 && p != NULL){j++;p = p->next;}if(p == NULL){return false;}else{s = (LinkNode*)malloc(sizeof(LinkNode));s->data = e;s->next = p->next;p->next = s;return true;}
}

2.9 删除元素数据

//删除数据元素
bool listDelete(LinkNode *L,int i,ElemType *e){int j = 0;LinkNode *p = L,*q;if(i <= 0) return false;while(j < i-1 && p!= NULL){j++;p=p->next;}if(p == NULL){return false;} else {q = p->next;if(q == NULL)return false;e = q->next;p->next = q->next;free(q);return true;}
}

双链表的结构体

双链表的基本运算的实现

1.建立双链表

1.1头插法

//建立双链表——头插法
void CreatListF(DLinkNode *L, ElemType a[],int n)
{DLinkNode *s;L = (DLinkNode*)malloc(sizeof(DLinkNode));L->next = L->prior = NULL;for(int i = 0; i < n; i++){s = (DLinkNode*)malloc(sizeof(DLinkNode));  //在循环里面开辟内存，方便a[i]插入s->data = a[i];     s->next = L->next;  if(L->next != NULL)  //若 L 非空，则修改 L->next 的前驱指针{L->next->prior = s;}L->next = s;s->prior = L;}
}

1.2尾插法

//建立双链表——尾插法
void CreatListR(DLinkNode *L, ElemType a[],int n)
{DLinkNode *s,*r;L = (DLinkNode*)malloc(sizeof(DLinkNode));r = L:for(int i = 0; i < n; i++){s = (DLinkNode*)malloc(sizeof(DLinkNode));s->data = a[i];r->next = s;s->prior = r;r = s;}r->next = NULL;
}

2.双链表的基本运算

对于双链表的一些基本运算而言，比如求长度，取元素值，查找元素等与单链表相同，这里就不再展开了，但双链表的插入与删除结点就不同于单链表了，这里做详细说明

2.1 插入数据元素

//插入数据元素
bool ListInster(DLinkNode *L,int i, ElemType e)
{int j = 0;DLinkNode *p = L,*s;if (i <= 0) return false;while(j < i - 1 && p != NULL){j++;p = p->next;}if( p == NULL) return false;else{s = (DLinkNode*)malloc(sizeof(DLinkNode));s->data = e;s->next = p->next;if(p->next != NULL){p->next->prior = s;}s->prior = p;p->next = s;return true;}
}

2.2 删除数据元素

//删除数据元素
bool ListDelet(DLinkNode *L,ElemType *e)
{int j = 0;DLinkNode *p = L,*q;if(i <= 0)  return false;while(j < i-1 && p != NULL){j++;p = p->next;}if(p == NULL)  return false;else{q = p->next;if(q == NULL)    return false;e = q->data;p->next = q ->next;if(q->next != NULL)q->next->prior = p;free(q);}
}