参考《数据结构与算法分析-c语言描述》一书
1、抽象数据类型
抽象数据类型（abstract data type，ADT）是一些操作的集合。抽象数据类型是数学的抽象，在ADT的定义中根本没涉及如何实现操作的集合，这可以看作模块化设计的补充。
2、表ADT
我们将处理一般的形如A1，A2，A3.......AN的表。这个表的大小是N，我们称大小为0的表为空表。
2.1 链表的ADT：
链表由一系列不必再内存中相连的结构组成，每一个结构均包含表元素和指向包含该元素后继元的结构的指针，我们称之为Next指针。最后一个单元的Next指针指向NULL。我们通常给链表增加一个表头节点（header），这个表头节点解决了以下的问题：
1、如何在表的最前面插入元素。
2、删除第一个元素，因为改变了表的起始端，编程中的疏忽将会造成表的丢失。
那么具有表头的链表形式如下图所示：
带表头的链表
我们使用结构体来定义链表：
#include <stdio.h>
struct Node;
//将链表指针声明为PtrToNode
typedef sturct Node *PtrToNode;
//将链表表头元素声明为List
typedef PtrToNode List;
//将链表除表头外的元素声明为Postion
typedef PtrToNode Position;
//将指定的元素类型，声明为ElementType，这里是int
typedef int ElementType
struct Node{
ElementType Element;
Position Next;
}
接下来，我们实现一些基本的ADT操作。
链表的初始化：
List init()
{
List L;
L = (List)malloc(sizeof(struct Node));
if (L == NULL)
{
printf ("Out of space");
return NULL;
}
L -> Element = -999;
L -> Next = NULL;
return L;
}
链表的创建：
List Create(List L){
Position TmpCell;
ElementType X;
Position Cur = L;
printf("请输入数字,-1结束\n");
scanf("%d",&X);
while (X!=-1)
{
TmpCell = (Position)malloc(sizeof(struct Node));
TmpCell -> Element = X;
TmpCell -> Next = NULL;
Cur -> Next = TmpCell;
Cur = TmpCell;
scanf("%d",&X);
}
return L;
}
链表的打印：
void Print(List L)
{
Position P = L -> Next;
while (P!=NULL){
printf("%4d",P->Element);
P = P -> Next;
}
printf("\n");
}
链表的删除：
void DeleteList(List L){
Position P,Tmp;
P = L -> Next;
L -> Next = NULL;
while (P!=NULL)
{
Tmp = P->Next;
free(P);
P = Tmp
}
}
判断是否是空表：
int IsEmpty(List L)
{
return L->Next == NULL;
}
判断当前元素是否在链表的末尾：
int IsLast(Position P,List L)
{
return P->Next == NULL;
}
链表元素的查找：
Position Find(ElementType X,List L)
{
Position P = L -> Next;
while (P!=NULL && P->Element != X)
P = P -> Next;
return P;
}
链表元素的删除：
void Delete2(ElementType X,List L)
{
Position P = L -> Next;
Position Q = L;
while (P!=NULL && P->Element != X)
{
Q = P;
P = P -> Next;
}
if (P!=NULL)
{
Q -> Next = P -> Next;
free(P);
}
}
2.2 双向链表
双向链表
2.3 循环链表
循环链表
2.4 链表实现多项式求和计算
书中并没有给出具体的实现，这是小编自己编写的代码，望多指点：
#include <stdio.h>
#include <stdlib.h>
typedef struct Node * node;
struct Node{
int Coefficient;
int Exponent;
node Next;
};
//两个多项式相加
node add(node head1,node head2)
{
node head = (node)malloc(sizeof(struct Node));
head -> Coefficient = -999;
head -> Exponent = -999;
head -> Next = NULL;
node p1 = head1 -> Next;
node p2 = head2 -> Next;
node cur = head;
//循环判断，直到一个链表到尾部
while (p1!=NULL && p2!=NULL)
{
//如果p1的指数大于p2的指数
if (p1 -> Exponent > p2 ->Exponent)
{
node temp = (node)malloc(sizeof(struct Node));
temp -> Exponent = p1 ->Exponent;
temp -> Coefficient = p1 -> Coefficient;
temp -> Next = NULL;
cur -> Next = temp;
cur = temp;
p1 = p1 -> Next;
}
//如果p2的指数大于p1的指数
else if(p1 -> Exponent < p2 ->Exponent)
{
node temp = (node)malloc(sizeof(struct Node));
temp -> Exponent = p2 ->Exponent;
temp -> Coefficient = p2 -> Coefficient;
temp -> Next = NULL;
cur -> Next = temp;
cur = temp;
p2 = p2 -> Next;
}
//如果二者指数相等
else
{
int sum = p1 -> Coefficient + p2 -> Coefficient;
//求和不为0才可以
if (sum != 0)
{
node temp = (node)malloc(sizeof(struct Node));
temp -> Exponent = p1 -> Exponent;
temp -> Coefficient = sum;
temp -> Next = NULL;
cur -> Next = temp;
cur = temp;
}
p1 = p1 -> Next;
p2 = p2 -> Next;
}
}
//将没有循环完的部分加入到结果的尾部
if (p1!=NULL)
{
cur -> Next = p1;
}
if (p2 != NULL)
{
cur -> Next = p2;
}
return head;
}
//初始化链表
node init()
{
node L;
L = (node)malloc(sizeof(struct Node));
if (L == NULL)
{
printf ("Out of space");
return NULL;
}
L -> Coefficient = -999;
L -> Exponent = - 999;
L -> Next = NULL;
return L;
}
//创建链表
node Create(node L){
node TmpCell;
int coef,exp;
node Cur = L;
printf("请输入数字系数和指数，指数-1结束\n");
scanf("%d%d",&coef,&exp);
while (exp!=-1)
{
TmpCell = (node)malloc(sizeof(struct Node));
TmpCell -> Coefficient = coef;
TmpCell -> Exponent = exp;
TmpCell -> Next = NULL;
Cur -> Next = TmpCell;
Cur = TmpCell;
scanf("%d%d",&coef,&exp);
}
return L;
}
//打印链表
void Print(node L)
{
node P = L -> Next;
while (P!=NULL){
printf("%dx^%d+",P->Coefficient,P->Exponent);
P = P -> Next;
}
printf("\n");
}
//
int main()
{
node head1 = init();
Create(head1);
Print(head1);
node head2 = init();
Create(head2);
Print(head2);
node head = add(head1,head2);
Print(head);
}
如果你喜欢我写的文章，可以帮忙给小编点个赞或者加个关注，我一定会互粉的！
如果大家对数据结构感兴趣，欢迎跟小编进行交流，小编微信为sxw2251，加我要写好备注哟！：
我的微信
网友评论