线性表
顺序表的存储结构与实现：
#include<stdlib.h>
#include<stdio.h>
typedef int ElemType;
typedef struct
{
int n; //顺序表的长度
int maxLength; //顺序表的最大允许长度
ElemType *element; //ElemType是自定义类型，指针element指示顺序表的存储空间的首地址
} SeqList; //SeqList是类型名，可通过它定义相应变量
#define ERROR 0
#define OK 1
#define Overflow 2 //Overflow表示上溢
#define Underflow 3 //Underflow表示下溢
#define NotPresent 4 //NotPresent表示元素不存在
#define Duplicate 5 //Duplicate表示有重复元素
typedef int Status; //返回值类型Status为整型
//顺序表的初始化
Status Init(SeqList *L, int mSize)
{
L->maxLength = mSize;
L->n = 0;
L->element = malloc(sizeof(ElemType)*mSize); //动态生成一维数组空间 malloc：动态分配内存空间的函数
if (!L->element)
return ERROR;
return OK;
}
//查找
Status Find(SeqList L, int i, ElemType *x)
{
if (i<0 || i>L.n-1) //判断元素下标i是否越界
return ERROR;
*x = L.element[i]; //取出element[i]的值通过参数x返回
return OK;
}
//插入
Status Insert(SeqList *L, int i, ElemType x)
{
int j;
if (i<-1 || i>L->n - 1) //判断元素下标i是否越界
return ERROR;
if (L->n == L->maxLength) //判断顺序表存储空间是否已满
return ERROR;
for (j = L->n-1; j > i; j--)
L->element[j+1] = L->element[j]; //从后往前逐个后移元素
L->element[i+1] = x; //将新元素放入下标为i+1的位置
L->n = L->n +1; //说明表长度为n+1
return OK;
}
//删除
Status Delete(SeqList *L, int i)
{
int j;
if (i<0 || i> L->n - 1) //判断元素下标i是否越界
return ERROR;
if (!L->n) //判断顺序表存储空间是否为空
return ERROR;
for (j = i + 1; j < L->n; j++)
L->element[j - 1] = L->element[j]; //从前往后逐个前移元素
L->n --; //表长减1
return OK;
}
//输出
Status Output(SeqList L)
{
int i;
if (!L.n) //判断顺序表存储空间是否为空
return ERROR;
for (i = 0; i <= L.n - 1; i++)
printf("%d", L.element[i]); //从前往后逐个前移元素
printf("\n");
return OK;
}
//撤销：释放初始化运算中动态分配的数据元素存储空间，以防止内存泄漏
void Destroy(SeqList *L)
{
(*L).n = 0;
(*L).maxLength = 0;
free((*L).element); //free：释放内存区，使这部分内存被其他变量使用，无返回值
}
void main()
{
int i;
SeqList list;
Init(&list, 10); //对线性表的初始化
for (i = 0; i < 9; i++)
Insert(&list, i - 1, i); //对线性表中插入新元素 --在a[0]中插入0，依次循环
printf("输出插入线性表的元素：\n");
Output(list);
Delete(&list, 0); //删除线性表元素a[0]，
printf("输出经删除操作线性表的元素：\n");
Output(list);
Destroy(&list);
printf("输出经清空操作线性表的元素：\n");
Output(list);
}
单链表的存储与实现（不带表头结点）：
#include<stdlib.h>
#include<stdio.h>
typedef int ElemType;
typedef struct Node
{
ElemType element; //结点的数据域
struct Node *link; //结点的指针域，存放后继结点的地址
} Node;
typedef struct
{
struct Node * first; //头指针
int n; //单链表中元素的个数
} SingleList; //singleList是单链表类型
#define ERROR 0
#define OK 1
#define Overflow 2 //Overflow表示上溢
#define Underflow 3 //Underflow表示下溢
#define NotPresent 4 //NotPresent表示元素不存在
#define Duplicate 5 //Duplicate表示有重复元素
typedef int Status; //返回值类型Status为整型
//初始化：单链表初始化运算是构造一个空的单链表
Status Init(SingleList *L)
{
L->first = NULL;
L->n = 0;
return OK;
}
//查找：单链表不具备顺序表的可随机存储元素的特性，必须沿着单链表的头结点开始逐个计数进行查找
Status Find(SingleList L, int i, ElemType *x)
{
Node *p;
int j;
if (i < 0 || i>L.n - 1) //判断i是否越界
return ERROR;
p = L.first;
for (j = 0; j < i; j++) //从头结点开始查找ai
p = p->link;
*x = p->element; //通过x返回ai的值
return OK;
}
//单链表的插入
Status Insert(SingleList *L, int i, ElemType x)
{
Node *p, *q;
int j;
if (i<-1 || i>L->n - 1) //判断i是否越界
return ERROR;
p = L->first;
for (j = 0; j < i; j++) //从头结点开始查找ai
p = p->link;
q = malloc(sizeof(Node)); //生成新结点q
q->element = x;
if (i>-1)
{
q->link = p->link; //新结点插在p所指结点之后
p->link = q;
}
else
{
q->link = L->first; //新结点插在头结点之前，成为新的头结点
L->first = q;
}
L->n++;
return OK;
}
//单链表的删除
Status Delete(SingleList *L, int i)
{
int j;
Node *p, *q;
if (!L->n) //判断是否为空
return ERROR;
if (i<-1 || i>L->n - 1) //判断i是否越界
return ERROR;
q = L->first;
p = L->first;
for (j = 0; j < i - 1; j++)
q = q->link;
if (i == 0)
L->first = L->first->link; //删除的是头结点
else
{
p = q->link; //p指向ai
q->link = p->link; //从单链表中删除p所指向的结点
}
free(p); //释放p所指结点的存储空间
L->n--;
return OK;
}
//输出
Status Output(SingleList L)
{
Node *p;
if (!L.n) //判断是否为空
return ERROR;
p = L.first;
while (p)
{
printf("%d", p->element);
p = p->link;
}
return OK;
}
//撤销
void Destroy(SingleList *L)
{
Node *p;
while (L->first)
{
p = L->first->link; //保存后继结点地址，防止“断链”
free(L->first); //释放first所指结点的存储空间
L->first = p;
}
}
void main()
{
int i;
int x;
SingleList list;
Init(&list); //初始化带表头的单链表
for (i = 0; i < 9; i++)
Insert(&list, i - 1, i); //将0-8依次插入单链表
printf("the linklist is:");
Output(list); //输出单链表元素
Find(list, 0, &x); //查找a0元素，通过x输出
printf("\nthe linklist is:");
printf("%d\n",x);
Delete(&list, 0); //删除表头元素
printf("删除后表中的元素为：");
Output(list); //删除后输出表中元素
Destroy(&list);
}
带表头结点的单链表
#include<stdlib.h>
#include<stdio.h>
#defineERROR0
#defineOK1
#defineOverflow2 //Overflow表示上溢
#defineUnderflow3 //Underflow表示下溢
#defineNotPresent4 //NotPresent表示元素不存在
#defineDuplicate5 //Duplicate表示有重复元素
typedefintElemType; // 将 整型 int 关键字 重新命名为 Elemtype
typedefintStatus; // 将 整型 int 关键字 重新命名为 Status
typedefstructNode
{
ElemTypeelement; //结点的数据域
structNode*link; //结点的指针域，存放后继结点的地址
}Node;
typedefstruct
{
structNode*head; //表头结点
intn; //单链表中元素的个数
}HeaderList;
//初始化：构造一个仅带有一个表头结点的空的单链表
StatusInit(HeaderList*h)
{
h->head = (Node*)malloc(sizeof(Node)); //生成表头结点
if(!h->head)
returnERROR;
h->head->link =NULL; //设置单链表为空表
h->n = 0;
returnOK;
}
//插入
StatusInsert(HeaderList*h,inti,ElemTypex)
{
Node*p, *q;
if(i< -1 ||i>h->n - 1) //判断i是否越界
returnERROR;
p =h->head;
for(intj = 0; j <=i; j++) //从头结点开始查找ai
p = p->link;
q =(Node*) malloc(sizeof(Node)); //生成新结点q
//带表头结点的单链表每个结点之前都有前驱结点，所以不需要再考虑单独处理插入在头结点之前的情况
q->element =x;
q->link = p ->link;
p->link = q;
h->n++;
returnOK;
}
//删除
StatusDelete(HeaderList*h,inti)
{
intj;
Node*p, *q;
if(!h->n) //判断是否为空
returnERROR;
if(i<0||i>h->n - 1) //判断i是否越界
returnERROR;
//带表头结点的单链表每个结点之前都有前驱结点，所以不需要再考虑单独处理删除头结点之前的情况
q =h->head;
for(j = 0; j <i; j++)
q = q->link;
p = q->link; //p指向ai
q->link = p->link; //从单链表中删除p所指结点
free(p); //释放p所指结点的存储空间
h->n--;
returnOK;
}
//查找
StatusFind(HeaderListh,inti,ElemType*x)
{
Node*p;
intj;
if(i<0 ||i>h.n - 1) //判断i是否越界
returnERROR;
p =h.head->link;
for(j = 0; j <i; j++) //从头结点开始查找ai
p = p->link;
*x= p->element; //通过x返回ai的值
returnOK;
}
/*方法2：
//查找
Status Find(HeaderList L,int i,ElemType *x)
{
Node *p,*q;
int j;
if(i<0||i>L.n-1)
return ERROR;
p=L.head;
for(j=0;j<i;j++)
p=p->link;
q=p->link;
*x=q->element;
return OK;
}
*/
//输出
StatusOutput(HeaderListh)
{
Node*p;
if(!h.n) //判断是否为空
returnERROR;
p =h.head->link;
while(p)
{
printf("%d", p->element);
p = p->link;
}
returnOK;
}
/*方法2：
//输出
Status Output(HeaderList L)
{
Node *p,*q;
if(!L.n)
return ERROR;
p=L.head;
q=p->link;
while(q)
{
printf("%d",q->element);
q=q->link;
}
return OK;
}
*/
//撤销
voidDestroy(HeaderList*h)
{
Node*p;
while(h->head)
{
p =h->head->link; //保存后继结点地址，防止“断链”
free(h->head); //释放head所指结点的存储空间
h->head = p;
}
}
//主函数
voidmain()
{
inti;
intx;
HeaderListlist;
Init(&list); //初始化带表头的单链表
for(i = 0; i < 9;i++)
Insert(&list,i-1,i); //为单链表赋值 将0-8依次插入单链表
printf("该单链表的元素为：");
Output(list); //输出单链表元素
Delete(&list, 0); //删除头结点a0元素
printf("\n删除后表中的元素为：");
Output(list); //删除后输出表中元素
Find(list, 0, &x); //查找表头元素
printf("\n表头元素为：");
printf("%d\n", x);
Destroy(&list);
}
