顺序表的基本运算实现
假设表中数据元素的值为整数;
#define MAX 100 //定义表最大长度容量, 实际用不到那么多
//顺序表结构定义
typedef struct
{
int data[MAX]; //存放表结点
int length; //当前表长度
} SeqList;
//创建初始顺序表
SeqList *createList(int size)
{
int i;
SeqList *list;
list=(SeqList *)malloc(sizeof(SeqList)); //分配空间
printf("请输入顺序表中的整数, 元素个数为%d\n",size);
for(i=0;i
scanf("%d",&list->data[i]) ; //逐一向顺序表中输入元素
list->length=size; //顺序表的长度赋值
return list;
}
//打印顺序表中的现有元素
printList(SeqList *list)
{
int i;
printf("\n目前顺序表中有%d个元素\n", list->length);
printf("这些元素分别是:\n");
for(i=0;ilength;i++)
printf("%d ",list->data[i]); //依次打印输出顺序表中的元素
printf("\n");
}
//在顺序表中查找值为e 的元素, 并返回它在表中的位置
Int locate(SeqList *list, int e)
{
int i=0;
while(ilength && list->data[i]!=e)
i++ ; //依次比较顺序表中各个元素
if(ilength) return i+1; //找到元素的处理
else printf("找不到元素!\n",); //未找到元素的处理
}
//在表中第i 个元素之前插入新元素e
insert(SeqList *list, int i , int e)
{
int j;
if (ilist->length+1 ) //检查插入位置的合法性
printf("插入位置非法!不能插入\n!");
else if (list->length==MAX)
printf("表满,不能插入!\n"); //检查表空满情况
else {for(j=list->length-1;j>=i-1;j--)
list->data[j+1]=list->data[j];
//从第n 个元素开始到第i 个元素依次向后移动一个位置
list->data[i-1]=e; //新元素e 插入i 位置
list->length++; //表长加1
}
}
//删除表中第i 个元素
delete(SeqList *list, int i)
{
int j;
if (ilist->length ) printf("删除位置非法!不能删除!\n");
//检查删除位置的合法性
else if (list->length==0) printf("表空,不能删除!\n");
//检查表空满情况
else
{for(j=i;jlength;j++)
list->data[j-1]=list->data[j];
//从第i 个元素开始到第n 个元素依次向前移动一个位置
list->length--; //表长减1
}
}
单链表的基本运算实现
以下算法都是带头结点的算法;
假设表中数据元素的值为整数;
//链表结点结构定义
typedef struct node
{
int data; //存放表结点值
struct node *next; //存放表结点的直接后驱元素的地址
} ListNode,*LinkList;
//头插法创建初始链表
LinkList create_h(int size)
{
LinkList head,p;
int i;
head=(LinkList)malloc(sizeof(ListNode));//申请头结点的存储空间
head->next=Null;//头结点的next 域为Null
printf("请输入这%d个元素的值:\n",size);
for(i=0;i
{
p=(LinkList)malloc(sizeof(ListNode));
scanf("%d",&p->data);
p->next=head->next;
head->next=p;
}
return head;
}
//尾插法创建初始链表
LinkList create_t(int size)
{
LinkList head,p,r;
int i;
head=(LinkList)malloc(sizeof(ListNode)); //申请头结点的存储空间
head->next=Null; //头结点的next 域为Null
r=head;//尾指针指向头结点
printf("请输入这%d个元素的值:\n",size);
for(i=0;i
{
p=(LinkList)malloc(sizeof(ListNode));
scanf("%d",&p->data);
p->next=Null;
r->next=p;
r=p;//尾指针指向新增结点
} return head; }
//求链表的长度
int length(LinkList head)
{
LinkList p;
int i;
p=head->next;//工作指针指向表中第一个结点
i=0;//计数器置0
while(p!=Null)
{
i++;//计数器计数
p=p->next;//工作指针后移到下一个结点
}
return i;
}
//打印链表中的现有元素
printList(LinkList head)
{
LinkList p;
p=head->next;//工作指针指向表中第一个结点
while(p!=Null)
{
printf("%d ",p->data);//打印当前指针所指结点的值
p=p->next;//工作指针后移到下一个结点
}
}
//按位查找元素
DataType get(LinkList head ,int i)
{
LinkList p;
int j;
p=head->next; //工作指针指向表中第一个结点
j=1; //计数器置1
while(p!=Null && j
{
p=p->next;
j++;
}
if(p!=Null && j==i) return p->data;//查找成功,p 指向第i 个结点, 返回第i 个结点值 else return Null;//i值非法, 查找失败
}
//按值查找元素
LinkList locate(LinkList head,int x)
{
LinkList p;
p=head->next;
while(p!=Null && p->data!=x)
p=p->next;
if (p!=Null && p->data==x)
{printf("找到该元素! ”);return p;}
else
{printf("找不到该元素!\n");return Null;}
}
//在链表中第i 个元素前插入新元素
insert(LinkList head,int i,int x)
{
LinkList p,s;
int j;
p=head;//工作指针指向头结点, 方便在第1个结点之前插入新元素 j=0;//计数器置0
while(p!=Null && j
p=p->next;
j++;
}
if (p!=Null && j==i-1)//定位成功
{
s=(LinkList)malloc(sizeof(ListNode));//申请新结点存储空间 s->data=x;
s->next=p->next;//新结点插入
p->next=s;//新结点插入
}
Else//插入位置非法
printf("插入位置非法!\n");
}
//在链表中删除第i 个结点元素
delete(LinkList head,int i)
{
LinkList p,q;
int j;
p=head; //工作指针指向头结点
j=0; //计数器置0
while(p->next!=Null && j
//将p 指针定位到第i 个结点的直接前驱接点上;
} { p=p->next; j++; } if(p->next!=Null && j==i-1) { q=p->next;//q指向要被删除的结点 p->next=q->next;//删除结点 free(q);//释放已被删除结点的存储空间 } else printf("空表或删除位置不合法!\n");
顺序表的基本运算实现
假设表中数据元素的值为整数;
#define MAX 100 //定义表最大长度容量, 实际用不到那么多
//顺序表结构定义
typedef struct
{
int data[MAX]; //存放表结点
int length; //当前表长度
} SeqList;
//创建初始顺序表
SeqList *createList(int size)
{
int i;
SeqList *list;
list=(SeqList *)malloc(sizeof(SeqList)); //分配空间
printf("请输入顺序表中的整数, 元素个数为%d\n",size);
for(i=0;i
scanf("%d",&list->data[i]) ; //逐一向顺序表中输入元素
list->length=size; //顺序表的长度赋值
return list;
}
//打印顺序表中的现有元素
printList(SeqList *list)
{
int i;
printf("\n目前顺序表中有%d个元素\n", list->length);
printf("这些元素分别是:\n");
for(i=0;ilength;i++)
printf("%d ",list->data[i]); //依次打印输出顺序表中的元素
printf("\n");
}
//在顺序表中查找值为e 的元素, 并返回它在表中的位置
Int locate(SeqList *list, int e)
{
int i=0;
while(ilength && list->data[i]!=e)
i++ ; //依次比较顺序表中各个元素
if(ilength) return i+1; //找到元素的处理
else printf("找不到元素!\n",); //未找到元素的处理
}
//在表中第i 个元素之前插入新元素e
insert(SeqList *list, int i , int e)
{
int j;
if (ilist->length+1 ) //检查插入位置的合法性
printf("插入位置非法!不能插入\n!");
else if (list->length==MAX)
printf("表满,不能插入!\n"); //检查表空满情况
else {for(j=list->length-1;j>=i-1;j--)
list->data[j+1]=list->data[j];
//从第n 个元素开始到第i 个元素依次向后移动一个位置
list->data[i-1]=e; //新元素e 插入i 位置
list->length++; //表长加1
}
}
//删除表中第i 个元素
delete(SeqList *list, int i)
{
int j;
if (ilist->length ) printf("删除位置非法!不能删除!\n");
//检查删除位置的合法性
else if (list->length==0) printf("表空,不能删除!\n");
//检查表空满情况
else
{for(j=i;jlength;j++)
list->data[j-1]=list->data[j];
//从第i 个元素开始到第n 个元素依次向前移动一个位置
list->length--; //表长减1
}
}
单链表的基本运算实现
以下算法都是带头结点的算法;
假设表中数据元素的值为整数;
//链表结点结构定义
typedef struct node
{
int data; //存放表结点值
struct node *next; //存放表结点的直接后驱元素的地址
} ListNode,*LinkList;
//头插法创建初始链表
LinkList create_h(int size)
{
LinkList head,p;
int i;
head=(LinkList)malloc(sizeof(ListNode));//申请头结点的存储空间
head->next=Null;//头结点的next 域为Null
printf("请输入这%d个元素的值:\n",size);
for(i=0;i
{
p=(LinkList)malloc(sizeof(ListNode));
scanf("%d",&p->data);
p->next=head->next;
head->next=p;
}
return head;
}
//尾插法创建初始链表
LinkList create_t(int size)
{
LinkList head,p,r;
int i;
head=(LinkList)malloc(sizeof(ListNode)); //申请头结点的存储空间
head->next=Null; //头结点的next 域为Null
r=head;//尾指针指向头结点
printf("请输入这%d个元素的值:\n",size);
for(i=0;i
{
p=(LinkList)malloc(sizeof(ListNode));
scanf("%d",&p->data);
p->next=Null;
r->next=p;
r=p;//尾指针指向新增结点
} return head; }
//求链表的长度
int length(LinkList head)
{
LinkList p;
int i;
p=head->next;//工作指针指向表中第一个结点
i=0;//计数器置0
while(p!=Null)
{
i++;//计数器计数
p=p->next;//工作指针后移到下一个结点
}
return i;
}
//打印链表中的现有元素
printList(LinkList head)
{
LinkList p;
p=head->next;//工作指针指向表中第一个结点
while(p!=Null)
{
printf("%d ",p->data);//打印当前指针所指结点的值
p=p->next;//工作指针后移到下一个结点
}
}
//按位查找元素
DataType get(LinkList head ,int i)
{
LinkList p;
int j;
p=head->next; //工作指针指向表中第一个结点
j=1; //计数器置1
while(p!=Null && j
{
p=p->next;
j++;
}
if(p!=Null && j==i) return p->data;//查找成功,p 指向第i 个结点, 返回第i 个结点值 else return Null;//i值非法, 查找失败
}
//按值查找元素
LinkList locate(LinkList head,int x)
{
LinkList p;
p=head->next;
while(p!=Null && p->data!=x)
p=p->next;
if (p!=Null && p->data==x)
{printf("找到该元素! ”);return p;}
else
{printf("找不到该元素!\n");return Null;}
}
//在链表中第i 个元素前插入新元素
insert(LinkList head,int i,int x)
{
LinkList p,s;
int j;
p=head;//工作指针指向头结点, 方便在第1个结点之前插入新元素 j=0;//计数器置0
while(p!=Null && j
p=p->next;
j++;
}
if (p!=Null && j==i-1)//定位成功
{
s=(LinkList)malloc(sizeof(ListNode));//申请新结点存储空间 s->data=x;
s->next=p->next;//新结点插入
p->next=s;//新结点插入
}
Else//插入位置非法
printf("插入位置非法!\n");
}
//在链表中删除第i 个结点元素
delete(LinkList head,int i)
{
LinkList p,q;
int j;
p=head; //工作指针指向头结点
j=0; //计数器置0
while(p->next!=Null && j
//将p 指针定位到第i 个结点的直接前驱接点上;
} { p=p->next; j++; } if(p->next!=Null && j==i-1) { q=p->next;//q指向要被删除的结点 p->next=q->next;//删除结点 free(q);//释放已被删除结点的存储空间 } else printf("空表或删除位置不合法!\n");