|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
通过这次的练习,虽然自己的自控力一般,容易被游戏,动漫吸引,但我发现数据结构和算法的学习是一个长期的过程。为了完成这次的练习,我复习了函数指针与指针函数的区别,也学习了插入排序算法。
- #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[L->length] = 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[i-1]); //q为插入位置
- for(p=&(L->elem[L->length-1]); 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[i]);
- 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[i-1]; //被删除元素的值赋给e
- for(; i<L->length; i++)
- {
- L->elem[i-1] = L->elem[i];
- }
- 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[i] < L.elem[i-1]){ //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入
- int j= i-1;
- int x = L.elem[i]; //复制为哨兵,即存储待排序元素
- L.elem[i] = L.elem[i-1]; //先后移一个元素
- while(j > -1 && x < L.elem[j]){ //查找在有序表的插入位置
- L.elem[j+1] = L.elem[j];
- j--; //元素后移
- }
- L.elem[j+1] = 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++);
- }
复制代码
参考资料:
排序算法
函数指针和指针函数 |
|