数据结构之线性表的顺序表示与实现
以下代码中包含了线性表的顺序表示与实现，包含元素的查找与删除，元素的添加，以及两个线性表合并，全部参考于《数据结构》
仅供参考
**************************************************************
* 声明：本文所有内容均为原创，转载请声明出处 *
* blog: http://blog.csdn.net/weixingstudio *
* watkins.song *
**************************************************************
// SeqList.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include "stdlib.h"#include "iostream"#define LIST_INIT_SIZE 100#define LIST_INCREMENT 50typedef int DataType;using namespace std;typedef struct{DataType *data;int length;int ListSize;}SeqList;int InitList_Seq(SeqList &L);int ListInsert_Seq(SeqList &L,int i, DataType e);int ListDelete_Seq(SeqList &L, int i, DataType &e);int LocateElem_Seq(SeqList L, DataType e, int (*compare)(DataType, DataType));int compare_elem(DataType a, DataType b);void MergeList_Seq(SeqList la, SeqList lb, SeqList &lc);int _tmain(int argc, _TCHAR* argv[]){int source[10]={102,88,2,34,17,97,23,89,55,10};SeqList L; // 定义一个顺序表InitList_Seq(L); // 初始化顺序表for(int i=1;i<=10;i++){ListInsert_Seq(L,i,source[i-1]);printf("%5d",source[i-1]);}printf("\n");for(int i=1;i<=L.length;i++){printf("%5d",L.data[i-1]);}printf("\n");// 删除一个元素测试DataType e;ListDelete_Seq(L,10,e);for(int i=1;i<=L.length;i++){printf("%5d",L.data[i-1]);}printf("\n");// 查找指定元素的位置int (*compare)(DataType, DataType)=compare_elem; // 定义一个指向函数的指针int tobefound=2;int position=LocateElem_Seq(L,tobefound,compare);printf("the position of 2 is :%3d\n", position);// 合并两个已经排好序的顺序线性表SeqList la;InitList_Seq(la);SeqList lb;InitList_Seq(lb);SeqList lc;InitList_Seq(lc);int sa[5]={7,18,89,201,222};int sb[7]={1,8,19,72,111,234,444};for(int i=1;i<=5;i++){ListInsert_Seq(la,i,sa[i-1]);}for(int i=1;i<=7;i++){ListInsert_Seq(lb,i,sb[i-1]);}MergeList_Seq(la,lb,lc);printf("/////////////////////////////////////////////////////////////////\n");printf("merged list\n");for(int i=0;i<lc.length;i++){printf("%4d",lc.data[i]);}getchar();return 0;}// 初始化顺序表int InitList_Seq(SeqList &L){// 分配一个空的线性表空间L.data=(DataType *)malloc(LIST_INIT_SIZE * sizeof(DataType));if(!L.data){// 分配空间失败return 0;}L.length=0;L.ListSize=LIST_INIT_SIZE;return 1; // 分配空间成功}// 在指定位置插入元素, 指定的位置为1-n，对于用户来说，数组从1开始// 插入元素后，需要将后面的所有元素向后移动int ListInsert_Seq(SeqList &L,int i, DataType e){// 如果插入位置在最后一个元素之后, 则直接插入，不用移动元素if(i==L.length+1){L.data[i-1]=e;L.length++;return 1;}// 判断插入位置是否合法,在第i个元素之前插入数据if(i<1||i>L.length) {// 插入位置出错return 0;}// 当前存储空间已满，分配新的存储空间if(L.length>=L.ListSize){DataType *newbase;newbase=(DataType *)realloc(L.data,(L.ListSize+LIST_INCREMENT)*sizeof(DataType));if(!newbase){// 新的储存空间分配失败return 0;}L.data=newbase;L.ListSize+=LIST_INCREMENT;}// 获取插入位置DataType *q=&(L.data[i-1]);DataType *p; // 最初指向最后以后元素 for(p=&(L.data[L.length-1]);p>=q;--p){*(p+1)=*p; // 将数组元素向后移动}// 插入指定的元素*q=e;L.length++;return 1;}// 在顺序表中删除指定位置的元素// 通过DataType &e 引用类型返回删除的元素的值// 删除元素之后需要将被删除元素后面的所有元素向前移动int ListDelete_Seq(SeqList &L, int i, DataType &e){// 判断删除元素的指定位置是否合法if(i<1||i>L.length){return 0;}// 判断是否是最后一个元素，也可以不进行判断，不进行判断的程序也是正确的if(i==L.length){DataType *p=&(L.data[i-1]);//指向被删除的元素e=*p;--L.length;return 1;}DataType *p=&(L.data[i-1]);//指向被删除的元素e=*p;DataType *q=L.data+L.length-1; // 指向最后一个元素for(++p;p<=q;++p){*(p-1)=*p; // 将元素向前移动}--L.length;return 1;}// 查找指定的元素int LocateElem_Seq(SeqList L, DataType e, int (*compare)(DataType, DataType)){// int i=1;DataType *p=L.data; // 指向第一个元素while(i<=L.length&&!(*compare)(*p++,e)) // 通过指向函数的指针调用函数{// 继续查找下一个元素++i;}if(i<=L.length){return i; }else{return -1; // 找不到返回-1}}// 比较函数int compare_elem(DataType a, DataType b){// 比较数据if(a==b)return 1;elsereturn 0;}// 合并两个顺序线性表// 合并以后的线性表按照非递减的顺序排列void MergeList_Seq(SeqList la, SeqList lb, SeqList &lc){// 对两个顺序表进行合并，并返回lcDataType *pa=la.data; // 指向la的数据的指针DataType *pb=lb.data;lc.ListSize=lc.length=la.length+lb.length;DataType *pc=lc.data=(DataType *)malloc(lc.ListSize*sizeof(DataType));if(!lc.data) return;DataType *pa_last=la.data+la.length-1;DataType *pb_last=lb.data+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++;}