线性表的顺序表示和c实现
通过这次的练习，虽然自己的自控力一般，容易被游戏，动漫吸引，但我发现数据结构和算法的学习是一个长期的过程。为了完成这次的练习，我复习了函数指针与指针函数的区别，也学习了插入排序算法。#include <stdio.h>
#include <stdlib.h>
//------线性表的动态分配顺序存储结构------
#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int elemType;//考虑到可扩展性，定义数据元素类型
typedef int Status;
typedef struct {
elemType * elem;//存储空间基址
int length;//当前长度
int listsize;//当前分配的存储容量（以sizeof(elemType)为单位）
}SqList;
Status InitList_Sq(SqList * L);
void InsertLast(SqList * L, elemType e);
Status ListInsert_Sq(SqList * L, int i, elemType);
Status ListDelete_Sq(SqList * L, int i, elemType *e);
Status AgainMalloc(SqList * L);
void TraverseList(SqList * L);
int LocateElem_Sq(SqList L, elemType e,
Status (* compare)(elemType, elemType));
Status compare(elemType a, elemType b);
void InsertSort(SqList L);
void MergeList_Sq(SqList La, SqList Lb, SqList* Lc);
int main()
{
int i;
int tmp;
SqList list1;
InitList_Sq(&list1);
//向线性表插入元素
printf("尾插法插入e，输入e(输q退出):");
while(scanf("%d",&tmp))
{
InsertLast(&list1, tmp);
printf("头插法插入e，输入e(输q退出):");
}
printf("插入元素后的list1:");
TraverseList(&list1);
getchar();
//在顺序表中第i个位置之前插入新的元素e
printf("输入i(输q退出)：");
while(scanf("%d", &i))
{
printf("输入元素e：");
scanf("%d", &tmp);
ListInsert_Sq(&list1, i, tmp);
printf("输入i(输q退出)：");
}
printf("插入元素后的list1:");
TraverseList(&list1);
getchar(); //为了缓冲
printf("删除一个元素\n");
printf("输入i：");
scanf("%d", &i);
ListDelete_Sq(&list1, i, &tmp);
printf("删除一个元素后的线性表list1=");
TraverseList(&list1);
printf("删除的元素e: %d\n", tmp);
SqList list2;
InitList_Sq(&list2);
//向线性表插入元素
printf("尾插法插入e，输入e(输q退出):");
while(scanf("%d",&tmp))
{
InsertLast(&list2, tmp);
printf("头插法插入e，输入e(输q退出):");
}
printf("插入元素后的list2:");
TraverseList(&list2);
printf("排序线性表:\n");
InsertSort(list1);
printf("排序后的线性表list1:");
TraverseList(&list1);
InsertSort(list2);
printf("排序后的线性表list2:");
TraverseList(&list2);
SqList list3;
InitList_Sq(&list3);
MergeList_Sq(list1, list2, &list3);
printf("list1和list2的合集list3=");
TraverseList(&list3);
}
// 构造一个空的线性表L。
Status InitList_Sq(SqList * L)
{
L->elem = (elemType * )malloc(LIST_INIT_SIZE*sizeof(elemType));
if(!L->elem) exit(OVERFLOW);
L->length = 0;
L->listsize = LIST_INIT_SIZE;
return OK;
}
//向表尾插入元素
void InsertLast(SqList * L, elemType e)
{
if(L->length >= L->listsize)
AgainMalloc(L);
L->elem = e;
L->length++;
return;
}
// 在顺序线性表L中第i个位置之前插入新的元素e,
// i的合法值为1=<i<=ListLength_Sq(L)+1
Status ListInsert_Sq(SqList * L, int i, elemType e)
{
elemType * q, * p;
if(i<1 || i>L->length+1) return ERROR;
if(L->length >= L->listsize) //当前存储空间已满,增加分配
AgainMalloc(L);
q = &(L->elem); //q为插入位置
for(p=&(L->elem); p>=q; --p) *(p+1) = *p;
//插入位置及之后的元素右移
*q = e;
++L->length;
return OK;
}
Status AgainMalloc(SqList * L) //空间不够时重新分配空间的函数
{
elemType * newbase; //分配一个临时基址
newbase = (elemType *)realloc(L->elem, (L->listsize+LISTINCREMENT)*sizeof(elemType));
if(!newbase) exit(OVERFLOW);
L->elem = newbase; //新基址
L->listsize += LISTINCREMENT;
return OK;
}
void TraverseList(SqList * L)
{
int i;
for(i=0; i<L->length; i++)
printf("%d ", L->elem);
printf("\n");
return;
}
Status ListDelete_Sq(SqList * L, int i, elemType * e)
{
//在顺序表L中删除第i个元素，并用e返回其值
//i的合法值为1=<i<=ListLength_Sq(L)
if((i<1) || (i>L->length)) return ERROR; //i值不合法
*e = L->elem; //被删除元素的值赋给e
for(; i<L->length; i++)
{
L->elem = L->elem;
}
L->length--;
return OK;
}
int LocateElem_Sq(SqList L, elemType e,
Status (* compare)(elemType, elemType))
{
//在顺序表L中查找第1个值与e满足compare()的元素的位符
//若找到，则返回其在L中的位序，否则返回0
int i = 1;
elemType * p = L.elem;
while(i<=L.length && !compare(*(p++), e)) ++i; //(*compare)
if(i<=L.length) return i;
else return 0;
}
Status compare(elemType a, elemType b)
{
if(a==b) return OK;
else return ERROR;
}
void InsertSort(SqList L)
{
//递增排序线性表
for(int i=1; i<L.length; i++){
if(L.elem < L.elem){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
int j= i-1;
int x = L.elem; //复制为哨兵，即存储待排序元素
L.elem = L.elem; //先后移一个元素
while(j > -1 && x < L.elem){//查找在有序表的插入位置
L.elem = L.elem;
j--; //元素后移
}
L.elem = x; //插入到正确位置
}
}
}
void MergeList_Sq(SqList La, SqList Lb, SqList* Lc)
{
//已知顺序线性表La和Lb的元素按值非递减排列
//归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列
elemType * pa, * pb, *pc;
pa = La.elem; pb = Lb.elem;
Lc->listsize = Lc->length = La.length+Lb.length;
pc = Lc->elem = (elemType *)malloc(Lc->listsize*sizeof(elemType)); //可以两次调用malloc
if(!Lc->elem) exit(OVERFLOW);//存储分配失败
elemType * pa_last, * pb_last;
pa_last = La.elem + La.length - 1;
pb_last = Lb.elem + Lb.length - 1;
while(pa<=pa_last && pb<=pb_last)
{
if(*pa <= *pb) *(pc++) = *(pa++);
else *(pc++) = *(pb++);
}
while(pa<=pa_last) *(pc++) = *(pa++);
while(pb<=pb_last) *(pc++) = *(pb++);
}
参考资料：
排序算法
函数指针和指针函数
页:
[1]