C实现的静态顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。顺序表的存储特点是:只要确定了起始位置，表中任一元素地址都可以求出。在c中实现顺序表时，由于函数较多，所以把函数的实现放在头文件中，在主函数中进行单元函数测试。 SequenceList_Static.h #ifndef __SEQUENCELIST_STATIC_H__ #define __SEQUENCELIST_STATIC_H__ #include<stdio.h> #include<stdlib.h> #include<string.h> #include<assert.h> typedef int DataType;//用typedef有利于顺序表存储类型的修改 #define MAX 100// 利用宏定义使得顺序表存储容量修改方便 typedef struct SeqList { DataType arr[MAX]; int size; }SeqList, *pSeqList; //顺序表的基本操作 void InitSeqList(pSeqList pSeq); void PrintSeqList(SeqList Seq); void PushBack(pSeqList pSeq, DataType x); void PopBack(pSeqList pSeq); void PushFront(pSeqList pSeq, DataType x); void PopFront(pSeqList pSeq); void Insert(pSeqList pSeq,int pos,DataType x); int Find(SeqList Seq,DataType x); void Remove(pSeqList pSeq,DataType x); void RemoveAll(pSeqList pSeq,DataType x); void ReverseList(pSeqList pSeq); void SortList(pSeqList pSeq); int BinarySearch(SeqList Seq,DataType x); //顺序表的初始化 void InitSeqList(pSeqList pSeq) { assert(pSeq); memset(pSeq->arr,0,sizeof(pSeq->arr)); pSeq->size = 0; } //为了方便查看对顺序表进行打印 void PrintSeqList(SeqList Seq) { int i = 0; for(i = 0; i < Seq.size; i++) { printf("%d\t",Seq.arr[i]); } printf("over\n"); } //存放数据 void PushBack(pSeqList pSeq, DataType x) { assert(pSeq); if(pSeq->size >= MAX)//顺序表的存放都应该先判断顺序表是否已满 { printf("sequence list is full\n"); } pSeq->arr[pSeq->size++] = x; } void PopBack(pSeqList pSeq) { assert(pSeq); if(pSeq->size == 0) { printf("The sequencelist is empty\n"); } pSeq->size--; } void PushFront(pSeqList pSeq, DataType x) { int i = 0; assert(pSeq); if(pSeq->size == MAX) { printf("sequence list is full\n"); return; } for(i = pSeq->size; i > 0; i--) { pSeq->arr[i] = pSeq->arr[i-1]; } pSeq->arr[0] = x; pSeq->size++; } void PopFront(pSeqList pSeq) { int i = 0; assert(pSeq); if(pSeq->size == 0) { printf("The sequencelist is empty\n"); return; } for(i = 0; i < pSeq->size-1; i++) { pSeq->arr[i] = pSeq->arr[i+1]; } pSeq->size--; } void Insert(pSeqList pSeq,int pos,DataType x) { int i = 0; assert(pSeq); //插入的位置应该合法 assert((pos<pSeq->size) && (pos >= 0)); if(pSeq->size == MAX) { printf("The sequence list is full\n"); return; } for(i = pSeq->size; i>pos; i--) { pSeq->arr[i] = pSeq->arr[i-1]; } pSeq->arr[pos] = x; pSeq->size++; } int Find(SeqList Seq,DataType x) { int i = 0; for(i = 0; i<Seq.size; i++) { if(Seq.arr[i] == x) { return i; } return -1; } } void Remove(pSeqList pSeq,DataType x) { int pos = Find(*pSeq,x); int i = 0; assert(pSeq); if(pos != -1) { for(i = pos; i<pSeq->size; i++) { pSeq->arr[i] = pSeq->arr[i+1]; } } pSeq->size--; } void RemoveAll(pSeqList pSeq,DataType x) { int i = 0; int j = 0; assert(pSeq); for(i =0 ; i<pSeq->size; i++) { if(pSeq->arr[i] == x) { for(j = i; j<pSeq->size; j++) { pSeq->arr[j] = pSeq->arr[j+1]; } pSeq->size--; } } } void ReverseList(pSeqList pSeq) { int start = 0; int end = pSeq->size-1; DataType tmp = 0; while(start < end) { tmp = pSeq->arr[start]; pSeq->arr[start] = pSeq->arr[end]; pSeq->arr[end] = tmp; start++; end--; } } //冒泡排序 void SortList(pSeqList pSeq) { int i = 0; int j = 0; assert(pSeq); for(i = 0; i<pSeq->size-1; i++) { for(j = 0; j<pSeq->size-1-i; j++) { if(pSeq->arr[j] > pSeq->arr[j+1]) { DataType tmp = pSeq->arr[j]; pSeq->arr[j] = pSeq->arr[j+1]; pSeq->arr[j+1] = tmp; } } } } int BinarySearch(SeqList Seq,DataType x) { int left = 0; int right = Seq.size-1; while(left <= right)//应该注意边界条件 { int mid = left-((left - right)>>1); if(Seq.arr[mid] > x) { right = mid - 1; } else if(Seq.arr[mid] == x) { return mid; } else { left = mid + 1; } } return -1; } #endif//__SEQUENCELIST_STATIC_H__ 以下是对函数的测试： test.c #include "SequenceList_Static.h" void Test1() { SeqList myseqlist; InitSeqList(&myseqlist); PushBack(&myseqlist,1); PushBack(&myseqlist,2); PushBack(&myseqlist,3); PrintSeqList(myseqlist); } void Test2() { SeqList myseqlist; InitSeqList(&myseqlist); PushBack(&myseqlist,1); PushBack(&myseqlist,2); PushBack(&myseqlist,3); PrintSeqList(myseqlist); PopBack(&myseqlist); PrintSeqList(myseqlist); } void Test3() { SeqList myseqlist; InitSeqList(&myseqlist); PushFront(&myseqlist,3); PushFront(&myseqlist,2); PushFront(&myseqlist,1); PushFront(&myseqlist,0); PrintSeqList(myseqlist); } void Test4() { SeqList myseqlist; InitSeqList(&myseqlist); PushFront(&myseqlist,3); PushFront(&myseqlist,2); PushFront(&myseqlist,1); PushFront(&myseqlist,0); PrintSeqList(myseqlist); PopFront(&myseqlist); PopFront(&myseqlist); PopFront(&myseqlist); PopFront(&myseqlist); PopFront(&myseqlist); PrintSeqList(myseqlist); } void Test5() { SeqList myseqlist; InitSeqList(&myseqlist); PushBack(&myseqlist,1); PushBack(&myseqlist,2); PushBack(&myseqlist,3); PrintSeqList(myseqlist); Insert(&myseqlist,0,0); PrintSeqList(myseqlist); } void Test6() { SeqList myseqlist; InitSeqList(&myseqlist); PushBack(&myseqlist,1); PushBack(&myseqlist,2); PushBack(&myseqlist,3); PrintSeqList(myseqlist); Remove(&myseqlist,1); PrintSeqList(myseqlist); } void Test7() { SeqList myseqlist; InitSeqList(&myseqlist); PushBack(&myseqlist,1); PushBack(&myseqlist,2); PushBack(&myseqlist,3); PrintSeqList(myseqlist); ReverseList(&myseqlist); PrintSeqList(myseqlist); } void Test8() { SeqList myseqlist; InitSeqList(&myseqlist); PushBack(&myseqlist,2); PushBack(&myseqlist,5); PushBack(&myseqlist,1); PushBack(&myseqlist,3); PushBack(&myseqlist,4); PrintSeqList(myseqlist); SortList(&myseqlist); PrintSeqList(myseqlist); } void Test9() { int ret = 0; SeqList myseqlist; InitSeqList(&myseqlist); PushBack(&myseqlist,1); PushBack(&myseqlist,2); PushBack(&myseqlist,3); PushBack(&myseqlist,4); PushBack(&myseqlist,5); PrintSeqList(myseqlist); ret = BinarySearch(myseqlist,5); printf("%d\n",ret); } void Test10() { SeqList myseqlist; InitSeqList(&myseqlist); PushBack(&myseqlist,1); PushBack(&myseqlist,2); PushBack(&myseqlist,3); PushBack(&myseqlist,1); PushBack(&myseqlist,5); PrintSeqList(myseqlist); RemoveAll(&myseqlist,1); PrintSeqList(myseqlist); } int main() { Test10(); system("pause"); return 0; }

相关阅读