线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、排序
线性表
线性表(顺序表示)
线性表是具有相同特性元素的一个有限序列,数据元素之间是线性关系,起始元素称为线性起点,终端元素称为线性终点。
线性表的顺序表示又称为顺序存储结构或者顺序映像。顺序存储的定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
顺序表的特点是:1、以物理位置表示相邻的逻辑关系;2、任意的元素均可以快速访问,故称为随机存取。
顺序表(Sequence List)的类型定义模板:
//顺序表定义模板
#define LIST_INIT_SIZE 100 //顺序表存储空间的初始分配
typedef struct {ElemType* elem; //数据指针,动态分配存储空间int length; //当前的长度
} SqList;
使用类型定义模板的案例:
//头文件包含
#include <stdio.h>
#include <stdlib.h>
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型,其值是函数结果状态代码
typedef int Status;
typedef char ElemType;
//顺序表的定义
#define MAXSIZE 100
typedef struct {ElemType* elem;int length;
} SqList;//顺序表的初始化函数
Status InitList_Sq(SqList* L)
{L->elem = (ElemType*)malloc(MAXSIZE * sizeof(ElemType));if (!L->elem)exit(OVERFLOW);L->length = 0;return OK;
}
//销毁线性表
void DestroyList_Sq(SqList* L)
{if (L->elem)free(L->elem);L = NULL;
}
//清空线性表
void ClearList(SqList* L)
{L->length = 0;
}
//求线性表的长度
int GetLength(const SqList* L)
{return L->length;
}
//判断线性表是否为空
Status IsEmpty(const SqList* L)
{if (L->length == 0)return TRUE;elsereturn FALSE;
}
//线性表取第i个值
Status GetElem(const SqList* L, int i, ElemType e)
{if (i<1 || i>L->length)return ERROR;else{e = L->elem[i - 1];return OK;}
}
//线性表按值顺序查找
Status LocateElem(const SqList* L, const ElemType e)
{int i;for (i = 0; i <= L->length - 1; i++){if (L->elem[i] == e)return i + 1; //查找成功返回元素位置}return 0; //查找失败返回0
}
//顺序表的插入
Status InsertList_Sq(SqList* L, int n, const ElemType e)
{int i;if (n >= 1 && n <= L->length + 1) //判断插入位置是否合法{if (L->length == MAXSIZE) //判断存储空间是否已满return ERROR;for(i=L->length-1; i>=n-1; i--) //插入位置及之后元素后移{L->elem[i+1] = L->elem[i];}L->elem[n - 1] = e;L->length += 1;return OK;}return ERROR;
}
//顺序表删除
Status DeleteElem(SqList* L, int n)
{int i;if (n >= 1 && n <= L->length){L->elem[n - 1] = 0; //删除指定元素for (i = n - 1; i <= L->length - 1; i++) //剩余元素移位{L->elem[i] = L->elem[i + 1];}L->length--; //顺序表长度-1return OK;}return ERROR;
}
//顺序表显示
void ShowList_Sq(const SqList* L)
{if (L->length == 0)puts("The SqList is empty!");else{int i;for (i = 0; i < L->length; i++){printf("%d ", L->elem[i]);}putchar('\n');printf("The length of SqList is %d\n", L->length);}
}
//合并两个顺序表,将L2合并到L1中
Status MergeList_Sq(SqList* L1, const SqList* L2)
{if (L1->length == 0 || L2->length == 0){puts("Length must be non-zero!");return ERROR;}else if (L1->length + L2->length > MAXSIZE){puts("Overflow");return OVERFLOW;}else {int i;for (i = 0; i <= L2->length - 1; i++){L1->elem[i + L1->length] = L2->elem[i];}L1->length += L2->length;return OK;}
}
int main(void)
{SqList my_list;ElemType a, b, c, d, e, f;a = 1;b = 2;c = 3;d = 4;e = 5;f = 6;SqList my_list2;InitList_Sq(&my_list);InsertList_Sq(&my_list, 1, a);InsertList_Sq(&my_list, 2, b);InsertList_Sq(&my_list, 3, c);InsertList_Sq(&my_list, 1, d);InsertList_Sq(&my_list, 2, e);InsertList_Sq(&my_list, 3, f);//printf("%d\n", LocateElem(&my_list, a));//ShowList_Sq(&my_list);//DeleteElem(&my_list, 2);ShowList_Sq(&my_list);InitList_Sq(&my_list2);InsertList_Sq(&my_list2, 1, a);InsertList_Sq(&my_list2, 2, b);InsertList_Sq(&my_list2, 3, c);ShowList_Sq(&my_list2);MergeList_Sq(&my_list, &my_list2);ShowList_Sq(&my_list);return 0;
}
顺序表的优缺点
优点:1、存储密度大;2、可以随机存取表中任一元素。
缺点:1、在插入、删除某一元素时,需要移动大量其他元素;2、浪费大量存储空间;3、属于静态存储形式,数据元素的个数不能够自由扩充。
线性表(链式表示)
链式存储结构的特点:
1、结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻。线性表的链式表示又称为非顺序映像或链式映像。
2、访问时只能通过头指针进入链表,并通过每个结点的指针域依次向后顺序扫描其余结点,所以寻找第一个结点和最后一个结点所花费的时间不等,这种存取元素的方式称为顺序存取。
链表(Link List)的分类:单链表、双链表、循环链表
a、单链表的实现
// 链表定义模板
typedef struct Lnode {ElemType data;struct Lnode* next; //注意这里需要struct关键字
}Lnode, *LinkList;
单链表基本操作的实现
单链表实现完整算法
//头文件导入
#include <stdio.h>
#include <stdlib.h>
//函数结果状态代码
#define OK 1
#define ERROR 0
//Status 是函数的类型,其值是函数结果状态代码
typedef int Status;
typedef int ElemType;
//单链表
typedef struct Signle_Link_List{ElemType data;struct LNode* next;
} LNode, *LinkList;//创建空链表
Status InitLinkList(LinkList* L)
{*L = (LinkList)malloc(sizeof(LNode));if (*L == NULL)return ERROR;(*L)->next = NULL;return OK;
}
//判断链表是否为空
int IsEmptyLinkList(const LinkList* L)
{if ((*L)->next == NULL)return 1;elsereturn 0;
}
//单链表的销毁
Status DestoryLinkList(LinkList* L)
{LNode* p;while (*L != NULL){p = *L;*L = (*L)->next;free(p);}return OK;
}
//清空单链表
Status ClearLinkList(LinkList* L)
{LNode* p, * q;q = (*L)->next;while (q != NULL){p = q;q = q->next;free(p);}(*L)->next = NULL;return OK;
}
//求单链表的表长
int LenLinkList(const LinkList* L)
{LNode* p;p = (*L)->next;int i = 0;while (p){i++;p = p->next;}(*L)->data = i; //将长度存储到L头结点的数据域中return i;
}
//取出单链表中第i个元素
Status LocateElem(const LinkList *L, int i, ElemType *e)
{int j = 1;LNode* p;p = (*L)->next;while (p && j < i){j++;p = p->next;}if (!p || j > i) //如果待查找的元素大于链表长度或者小于1,查找错误return ERROR;*e = p->data;return OK;
}
//单链表按值查找,返回LNode
LNode* LocateElem_V_LNode(const LinkList *L, ElemType value)
{LNode* p;p = (*L)->next;while (p && p->data != value) //p不为空指针,并且没找到{p = p->next;}return p; //找到返回结点的地址,没找到返回NULL
}
//单链表按值查找,返回元素位置
int LocateElem_V_Index(const LinkList *L, ElemType value)
{int j = 1;LNode* p;p = (*L)->next;while (p && p->data != value){j++;p = p->next;}if (!p)return 0; //没找到,返回0elsereturn j; //找到,返回第几个结点
}
//单链表插入,在第i个结点之前插入一个结点
Status InsertLinkList(LinkList *L, int i, ElemType value)
{LNode* p;p = (*L)->next;int j = 1;while (p && j < i - 1) //找到第i-1个结点{j++;p = p->next;}if (!p || j > i - 1) //i大于表长+1,或者小于1,插入位置非法return ERROR;LNode* newlnode;newlnode = (LNode*)malloc(sizeof(LNode));newlnode->data = value;newlnode->next = p->next;p->next = newlnode;return OK;
}
//单链表删除,删除第i个结点
Status DeleteLinkList(LinkList *L, int i)
{LNode* p, * q;int j = 1;p = (*L)->next;while (p && j < i - 1){j++;p = p->next;}if (!p || j > i - 1)return ERROR;q = p->next;p->next = q->next;free(q);return OK;
}
//单链表建立-头插法
void CreateLinkList_H(LinkList* L, int n)
{*L = (LinkList)malloc(sizeof(LNode));(*L)->next = NULL; //先建立一个头结点int i;for (i = n; i > 0; i--){LNode* newlnode;newlnode = (LNode*)malloc(sizeof(LNode));printf("Enter the node data:_____\b");scanf("%d", &newlnode->data);newlnode->next = (*L)->next;(*L)->next = newlnode;}
}
//单链表建立-尾插法
void CreateLinkList_R(LinkList *L, int n)
{*L = (LinkList)malloc(sizeof(LNode));(*L)->next = NULL; //先建立一个头结点LNode* p;p = *L;int i;for (i = n; i > 0; i--){LNode* newlnode;newlnode = (LNode*)malloc(sizeof(LNode));printf("Enter the node data:___\b");scanf("%d", &newlnode->data);newlnode->next = NULL;p->next = newlnode;p = p->next;}
}
//显示单链表
void ShowLinkList(const LinkList* L)
{LNode* p;p = (*L)->next;if (!p){puts("The LinkList is empty");return;}int i = 1;while (p){printf("%d : %d\n", i, p->data);i++;p = p->next;}putchar('\n');
}
//测试函数
int main(void)
{LinkList my_list;my_list = NULL;ElemType answer = 0;//InitLinkList(my_list);//CreateLinkList_H(&my_list, 3); //测试头插法建立链表CreateLinkList_R(&my_list, 3); //测试尾插法建立链表//ClearLinkList(&my_list); //测试清空链表ShowLinkList(&my_list);//DestoryLinkList(&my_list); //测试销毁链表printf("%s\n",IsEmptyLinkList(&my_list) >0?"LinkList is Empty":"LinkList isn't Empty"); //测试判断链表函数printf("The length of LinkList is %d\n", LenLinkList(&my_list)); //测试求长度函数LocateElem(&my_list, 3, &answer);printf("The %d elem is %d\n", 3, answer); //测试取元素函数LNode *answer1;answer1 = LocateElem_V_LNode(&my_list, 2);printf("The answer is %d\n", answer1->data); //测试取元素函数printf("The Index of 3 is %d\n", LocateElem_V_Index(&my_list, 3)); //测试取元素函数InsertLinkList(&my_list, 2, 10); //测试增加结点函数ShowLinkList(&my_list);DeleteLinkList(&my_list, 3); //测试删除结点函数ShowLinkList(&my_list); return 0;
}
b、单向循环链表的实现
c、双向链表的实现
//双向链表的定义
typedef struct DuLNode {ElemType data;struct DuLNode* prior, * next;
} DuLNode, *DuLinkList;
双向链表的操作
双向链表的插入
双向链表的删除