一、线性表顺序存储
1、顺序表的插入运算*
顺序表的插入运算 InsertSeqlist (SeqList L,DataType x,int i)是指在顺序表的第 i(1≤i≤ n+1)个元素之前，插入一个新元素 x。使长度为 n 的线性表（a1，a2，…，ai-1， ai， ai+1，.…，an)变为长度为 n+1 的线性表(a1，a2，…，ai-1，x， ai，ai+1，.…，an)。 插入算法的基本步骤是：首先将结点 ai~an 依次向后移动一个元素的位置，这样空出第 i 个数据元素的位置；然后将 x 置入该空位，最后表长加 1
void InsertSeqlist(SeqList L,DataType x, int i)
{
if(L.length == Maxsize) exit("表已满");
if(i<1 || i>L.length + 1) exit("位置错"); //检查插入位置是否合法
for(j = L.length; j>=i;j--) //初始 i=L.length
L.data[j] = L.data[j-1]; // 依次后移
L.data[i-1] = x; //元素 x 置入到下标为 i-1 的位置
L.length++ //表长度加 1
}
2、顺序表的删除*
删除运算 DeleteSeqlist(SeqList L,int i)是指将线性表的第 i(1≤i≤n)个数据元素删去，使 长度为 n 的线性表（a1，a2，…，ai-1， ai，ai+1，.…，an)变为长度为 n-1 的线性表(a1， a2，…，ai-1，ai+1，.…，an)。 删除运算的基本步骤是：①结点 ai+1,…，an 依次向左移动一个元素位置（从而覆盖掉被删 结点 ai）；②表长度减 1。此处无需考虑溢出，只判断参数 i 是否合法即可。
void DeleteSeqlist(SeqList L, int i)
{
if(i<1 || i>L.length) exit("位置错")
for(j=i;j < L.length; j++) // 第 i 个元素的下标为 i-1
L.data[j-1] = L.data[j] // 依次左移
L.length-- //表长度减 1
}
3、顺序表定位运算*
定位运算 LocateSeqlist(SeqList L,DataType x)的功能是查找出线性表 L 中值等于 x 的结 点序号的最小值，当找不到值为 x 的结点时，返回结果 0。下列算法从左往右扫描顺序表 中的元素，考察元素的值是否等于 x
int LocateSeqlist(SeqList L, DataType x)
{
int i = 0;
while((i < L.length) && (L.data[i] != x)) //在顺序表中查找值为 x 的结点
i++;
if(i< L.length) return i+1; //若找到值为 x 的元素，返回元素的序号
else return 0; // 未查找到值为 x 的元素，返回 0
}
二、单链表
1、单链表的类型定义
typedef struct node
{
DataType data; // 数据域
struct node * next; // 指针域
}Node,*LinkList
2、单链表初始化*
空表由一个头指针和一个头结点组成
在算法中，变量 head 是链表的头指针，它指向新创建的结点，即头结点。一个空单链表 仅有一个头结点，它的指针域为 NULL。
LinkList InitiateLinkList()
{
// 建立一个空的单链表
LinkList head; //头指针
head=malloc(sizeof(Node)); //动态构建一结点，它是头结点
head->next = NULL;
return head;
}
3、求表长
在单链表存储结构中，线性表的表长等于单链表中数据元素的结点个数，即除了头结点以外 的结点的个数。 设置一个工作指针 p，初始时，p 指向头结点，并设置一个计数器 cnt，初值设置为 0。然 后，让工作指针 p 通过指针域逐个结点向尾结点移动，工作指针每向尾部移动一个结点，让 计数器加 1。直到工作指针 p->next 为 NULL 时，说明已经走到了表的尾部，这时已完成 对所有结点的访问，计数器 cut 的值即是表的长度。
int lengthLinklist (LinkList head)
{ Node *p;
p=head; j=0;
while( p->next != NULL )
{ p=p->next;
j++;
}
return(j);
}
4、读表元素
通常给定一个序号 i，查找线性表的第 i 个元素。在链表中，任何相邻的两个结点通过一个 指针相连，一个结点的位置包含在直接前驱结点的 next 域中。所以，必须从头指针出 发，一直往后移动，直到第 i 个结点。
Node * GetlinkList(LinkList head, int i)
{
Node * p;
p=head->next; int c=1;
while((c<1)&&(p!=NULL))
{
p=p->next;
c++;
}
if(i==c) return(p);
else return NULL;
}
4、定位*
线性表的定位运算，就是对给定表元素的值，找出这个元素的位置。在单链表的实现中，则 是给定一个结点的值，找出这个结点是单链表的第几个结点。定位运算又称作按值查找。 在定位运算中，也需要从头至尾访问链表，直至找到需要的结点，返回其序号。若未找到， 返回 0。
int locateLinklist(LinkList head, DataType x)
{
Node * p=head; // p是工作指针
p=p->next; // 初始时p指向首结点
int i=0; // i代表序号这里初值为0
while(p!=NULL&&p->data!=x)
{
i++;
p=p->next;
}
if(p!=NULL) return i+1;
else return 0;
}
5、插入*
单链表的插入运算是将给定值为 x 的元素插入到链表 head 的第 i 个结点之前。
步骤：（1）先找到链表的第 i-1 个结点 q。（2）生成一个值为 x 的新结点 p，(3) p 的指针域指 向 q 的直接后继结点。
void InsertLinklist(LinkList head, DataType x,int i)
{
//在表 head 的第 i 个数据元素结点之前插入一个以 x 为值的新结点
Node *p,*q;
if(i==1) q=head;
else q=GetLinklist(head,i-1) //找第 i-1 个数据元素结点
if(q==NULL)//第 i-1 个结点不存在
exit("找不到插入的位置");
else
{
p=malloc(sizeof(Node));p->data =x; //生成新结点
p->next = q->next; //新结点链域指向*q 的后继结点
q->next = p; //修改*q 的链域
}
}
注意：链接操作 p->next=q->next 和 q->next=p 两条语句的执行顺序不能颠倒，否则结 点*q 的链域值（即指向原表第 i 个结点的指针）将丢失。
6、删除
删除运算是给定一个值 i，将链表中第 i 个结点从链表中移出，并修改相关结点的指针域， 以维持剩余结点的链接关系。
将 ai结点移出后，需要修改该结点的直接前驱结点的 指针域，使其指向移出结点 ai的直接后继结点。
void DeleteLinklist(LinkList head, int i)
{
Node *q;
if(i==1) q=head;
else q=GetLinklist(head, i-1); //先找待删结点的直接前驱
if(q!==NULL&&q->next!=NULL) //若直接前驱存在且待删结点存在
{
p=q->next; //p 指向待删结点
q->next = p->next; //移出待删结点
free(p); //释放已移出结点 p 的空间
}
else exit("找不到要删除的结点");
}
三、双向循环链表
1、插入语句
在 p 所指结点的后面插入一个新结点*t，需要修改四个指针
(1) t->prior=p;
(2) t->next=p->next;
(3) p->next->prior=t;
(4) p->next=t
2、删除
(1) p->prior->next=p->next; //p 前驱结点的后链指向 p 的后继结点
(2) p->next->prior=p->prior; //p 后继结点的前链指向 p 的前驱结点
(3) free(p); //释放*p 的空间
四、栈
1、顺序栈类型定义
const int maxsize=6;
typedef struct seqstack {
DataType data[maxsize];
int top;
}SeqStk;
2、顺序栈初始化
int Initstack(SeqStk *stk)
{
stk->top=0;
return 1;
}
3、顺序栈判断栈空
int EmptyStack(SeqStk *stk)
{
if(stk->top==0) return 1;
else return 0;
}
4、顺序栈进栈
int Push(SeqStk *stk,DataType x)
{
if(stk->top==maxsize-1) /*判是否上溢*/
{
error("栈满"); return 0; /*上溢*/
}
else
{
stk->top++;/*修改栈顶指针，指向新栈顶*/
stk->data[stk->top] = x;/*元素x插入新栈顶中*/
return 1;
}
}
5、顺序栈出栈
int Pop(SeqStk *stk)
{
if(stk->top == 0)/*判是否下溢*/
{
error("栈空"); return 0;/*下溢*/
}
else
{
stk->top--; /*修改栈顶指针，指向新栈顶*/
return 1;
}
}
6、顺序栈取栈顶元素
DataType GetTop(SeqStk *stk)
{
if(stk->top==0)
{
return NULLData;
}
else
{
return stk->data[stk->top]
}
}
7、链栈初始化
void InitStack(LkStk*LS) {
LS=(LkStk*)malloc(sizeof(LkStk))
LS->next = NULL
}
8、链栈判栈空
int EmptyStack(LkStk *LS)
{
if(LS->next == NULL) {
return 1;
} else {
return 0;
}
}
9、链栈进栈
void Push(LkStk *LS,DataType x)
{
LkStk*temp;
temp = (LkStk*)malloc(sizeof(LkStk));
temp->data=x;
temp->next=LS->next;
LS->next=temp;
}
10、链栈出栈
int Pop(Lkstk*LS)
{
LsStk*temp;
if(LS->next!== NULL)
{
temp=LS->next;
LS->next=temp->next;
free(p);
return 1;
}
else return 0;
}
11、链栈取栈顶元素
DataType GetTop(LkStk*LS)
{
if(LS->next==NULL)
return LS->next->data;
else
return NULLData;
}
五、队列
1、循环对列入队列
队尾指针增1
sq.rear=(sq.rear+1)%maxsize
2、循环对列出队列
sq.front=(sq.front+1)%maxsize
六、排序
1、冒泡排序
void BubbleSort(List R, int n) {
int i, j, temp, endSort;
for(i=1;i < n-1; i++) {
endSort = 0;
for(j=1;j < n-i;j++) {
if(R[j].key > R[j+1].key) {
temp = R[j].key;
R[j].key = R[j+1].key;
R[j+1].key = temp;
endSort = 1;
}
if(endSort == 0) break;
}
}
}
2、直接插入排序
void StraighInsertSort(List R, int n) {
int i, j;
for(i=2;i<=n;i++) {
R[0]=R[i];
j=i-1;
while(R[0].key<R[j].key) {
R[j+1]=R[j];
j--;
}
R[j+1]=R[0];
}
}
持续更新中...
网友评论