数据结构c语⾔版严蔚敏顺序表
说来惭愧由于贪玩，数据结构挂科了，现在重新学⼀遍数据结构，⽤博客督促⼀下⾃⼰，希望各位同学引以为戒，贪玩⼀时爽，痛苦永留存。
本⽂主要以严⽼师的数据结构书为主。
结构类型
listsize代表这个顺序表的最⼤容量  可以随时扩容
length代表表中元素个数  应⼩于listsize
1.初始化
Status list_init(SqList &L)
{
L.elem=(Elemtype *)malloc(MAXSIZE*sizeof(Elemtype));//开辟空间
if(!L.elem)
exit(OVERFLOW);
L.length=0; //初始化数据有效数据为0
L.listsize=MAXSIZE; //初始化数组长度为MAXSIZE
}
ps：exit函数其头⽂件为stdlib.h
退出程序返回OVERFLOW  OVERFLOW需要你⾃⼰宏定义  -2
在main.h中其被定义为3  不定义也可
2.顺序表的创建
Status CreateList(SqList &L)
{
printf("请您输⼊想要创建的顺序表的元素的个数:\n");
scanf("%d",&L.length);
printf("请输⼊你想要创建的顺序表:\n");
for(int i=0;i<L.length;i++)
scanf("%d",&L.elem[i]);
}
3.顺序表的取值
Status GetElem(SqList L,int i,ElemType &e)
{
if(i<1 || i>L.length) //判断i值是否合理，如果不合理，返回0
return 0;
e = L.elem[i-1]; //elem[i-1]单元存储第i个数据元素
return 1;
}
4.顺序表的查
//在顺序表L中查值为e的数据元素并返回其序号
Status LocateElem(SqList L,ElemType e)
{
for(int i=0;i<L.length;i++)
{
if(L.elem[i] == e)
return i+1; //查成功，返回序号i+1
}
return 0;
}
个⼈认为这样编写更简洁优雅
下⾯是按照书上的
⾸先，先定义⼀下Compare()这个函数，就假设这个关系是相等关系吧，利⽤Compare这个函数实现，如果两个指针中的值相等就返回true，不相等就返回false。代码如下：
bool Compare(ElemType* e1,ElemType* e2)    //参数要就都⽤指针表⽰，以免函数间相互调⽤时参数出现不匹配问题
{
if(*e1==*e2)
return true;
else
return false;
}
根据这个关系，要出顺序表中的元素，明显的思路就是⼀个个元素进⾏对⽐了，看是否满⾜Compare()关系。这⾥需要注意的⼀点是元素的位置和数组元素的表⽰，第i个位置的元素是(*L).elem[i-1]。代码如下：
int LocateElem(SqList *L,ElemType *e)
{
int i=1;      //i为顺序表中的位置
ElemType *p;  //p指向顺序表中位序为i的元素
p=(*L).elem;    //取数组⾸元素地址不⽤&
while(i<=(*L).length&&(!Compare(p,e)))
{
i++;
p++;
}
if(i<=(*L).length)
return i;      //返回满⾜条件的元素所在位置i
else
return 0;
}
ps：我刚开始不太⾸元素地址为啥不加&  后来才发现是数组没学好，数组名代表⾸地址，如果想深⼊
了解⼤家可以看看这个
明⽩bgnim5.顺序表的插⼊
//不考虑增加分配的简化版
Status ListInsert(SqList &L,int i,ElemType e)
{
//在顺序表L中第i个位置插⼊新的元素e,i值的合法范围是1<=i<=L.length+1
if((i<1) || (i>L.length+1))
c语言listinsert函数return 0; //i值不合法
if(L.length == MAXSIZE)
return 0; //当前的存储空间已经满了
for(int j=L.length-1;j>=i-1;j--)
L.elem[j+1] = L.elem[j]; //插⼊位置及其之后的元素后移
L.elem[i-1] = e; //将新的元素e放⼊第i个位置
L.length++; //表长加1
return 1;
}
Status ListInsert(SqList *L,int i,ElemType e) /* 算法2.4 */
{ /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1 */
/
* 操作结果：在L中第i个位置之前插⼊新的数据元素e，L的长度加1 */
ElemType *newbase,*q,*p;
if(i<1||i>(*L).length+1) /* i值不合法 */
return ERROR;
if((*L).length>=(*L).listsize) /* 当前存储空间已满，增加分配 */
{
newbase=(ElemType *)realloc((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase)
exit(OVERFLOW); /* 存储分配失败 */
(*L).elem=newbase; /* 新基址 */
(*L).listsize+=LISTINCREMENT; /* 增加存储容量 */
}
q=&(*L).elem[i-1]; /* q为插⼊位置 */
for(p=&(*L).elem[length];p>=q;--p) /* 插⼊位置及之后的元素右移 */
*(p+1)=*p;
*q=e; /* 插⼊e */
++(*L).length; /* 表长增1 */
return OK;
}
ps：如果想严格来说按书上应  Sqlist &L      把（*L）换成L即可        两者是等价的  都可以完成对原表的操作但切记  不⽤*L,&L⽽直接使⽤L按照函数形参  你是对实际L表的⼀个复制体进⾏了插⼊  对原表⽆影响
6.顺序表的删除
Status ListDelete(SqList *L,int i,ElemType *e)
{
ElemType *p,*q;
if(i<0||i>=(*L).length)
{
return error;
}
q=&((*L).elem[i-1]);  //q为被删除元素的位置
*e=*q;
p=&((*L).elem[(*L).length-1]);  //p指向顺序表最后⼀个元素位置的地址
for(q;q<p;q++)
{
*q=*(q+1);
}
(*L).length--;
return ok;
}
//简化不⽤e返回值时取巧直接前移覆盖
Status ListDelete(SqList &L,int i)
{
//在顺序表L中删除第i个元素，i值的合法范围是1<=i<=L.length
if((i<1) || (i>L.length))
return 0; //i值不合法
for(int j=i;j<=L.length-1;j++)
L.elem[j-1] = L.elem[j]; //被删除元素之后的元素前移
L.length--; //表长减1
return 1;
}
7.其他操作⽐较简单⼤家看看代码就⾏了
Status DestroyList(SqList *L)
{ /* 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L */
free((*L).elem);
(*L).elem=NULL;
(*L).length=0;
(*L).listsize=0;
return OK;
}
Status ClearList(SqList *L)
{ /* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
(*L).length=0;
return OK;
}
Status ListEmpty(SqList L)
{ /* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */  if(L.length==0)/*return L.length==0?TURE:FALSE；更简洁的表达*/
return TRUE;
else
return FALSE;
}
int ListLength(SqList L)
{ /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
return L.length;
}
Status ListTraverse_Sq(SqList L, void(Visit)(LElemType_Sq))
{
int i;
for(i=0; i<L.length; i++)
Visit(L.elem[i]);
return OK;
}//⽤visit函数访问表中元素
算法2.1║
╚════*/
void Union(SqList *La, SqList Lb)
{
int La_len, Lb_len;
int i;
LElemType_Sq e;
La_len = ListLength_Sq(*La);  //求顺序表长度
Lb_len = ListLength_Sq(Lb);
for(i=1; i<=Lb_len; i++)
{
GetElem_Sq(Lb, i, &e);    //取Lb中第i个元素赋给e
if(!LocateElem_Sq(*La, e, equal))  //若e不在La中则插⼊
ListInsert_Sq(La, ++La_len, e);
}
}
Status equal(LElemType_Sq e1, LElemType_Sq e2)
{
return e1==e2 ? TRUE : FALSE;
}
算法2.2║
╚════*/
void MergeSqList_1(SqList La, SqList Lb, SqList *Lc) //调⽤顺序表函数进⾏合并{
int La_len, Lb_len;
int i, j, k;
LElemType_Sq ai, bj;
i = j = 1;
k = 0;
InitList_Sq(Lc);    //初始化Lc
La_len = ListLength_Sq(La);  //获取La、Lb长度
Lb_len = ListLength_Sq(Lb);
while(i<=La_len && j<=Lb_len)  //La及Lb均未扫描完
{
GetElem_Sq(La, i, &ai);
GetElem_Sq(Lb, j, &bj);
if(ai<=bj)
{
ListInsert_Sq(Lc, ++k, ai);
i++;
}
else
{
ListInsert_Sq(Lc, ++k, bj);
j++;
}
}
while(i<=La_len)    //表La还未扫描完
{
GetElem_Sq(La, i++, &ai);

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。