找回密码
 注册
关于网站域名变更的通知
查看: 262|回复: 2
打印 上一主题 下一主题

线性表插入算法

[复制链接]

该用户从未签到

跳转到指定楼层
1#
发表于 2016-7-13 16:07 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式

EDA365欢迎您登录!

您需要 登录 才可以下载或查看,没有帐号?注册

x
在这种存储结构中,容易实现线性表的某些操作,如随机存取第i个数据元素等。只是要特别注意的是,C语言中数组的下标从“0”开始,因此,若L是SqList类型的顺序表,则表中第i个数据元素是L.elem[i-1]。下面重点讨论线性表的插入和删除两种操作在顺序存储表示时的实现方法。
' D, A3 l' z$ X( S+ A* Z线性表的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素,就是要使长度为n的线性表# g/ k' T! U  Y9 ?6 x! `
(a1,…,ai-1,ai,…,an)
' _; w+ }3 I% J8 T4 {; w变成长度为n+1的线性表
0 N  P+ L# A- F: a; N(a1,…,ai-1,b,ai,…,an)
6 E6 v- J5 T- ]: ?数据元素ai-1和ai之间的逻辑关系发生了变化。在线性表的顺序存储结构中,由于逻辑上相邻的数据元素在物理位置上也是相邻的,因此,除非i=n+1,否则必须移动元素才能反映这个逻辑变化的关系。
0 r2 r0 o: M9 @0 F7 A: f, k4 |" v一个线性表在进行插入操作的前、后,其数据元素在存储空间中的位置变化。为了才线性表的第4和第5个元素之间插入一个值为25的数据元素,则需将第5个至第8个数据元素依次往后移动一个位置。
1 r- g( T+ y) O0 n( d* P7 H/ j一般情况下,在第i(1≤i≤n)个元素之前插入一个元素时,需将第n至第i个元素向后移动一个位置。
7 Q0 e- ~4 t# E% A7 i$ LStatusListInsert_Sq(SqList &L,int i,ElemType){* R9 ]% A4 r- D8 x3 A! ?8 M
//在顺序线性表L中第i个位置之前插入新的元素e,
. K, W* \4 `  g8 H6 T8 [; ^* Z' N- }//i的合法值为1≤i≤ListLength——Sq(L)+13 b* K4 S7 W) |7 }
if(i<1||i>L.length+1)return ERROR;//i值不合法" c6 ^9 d. t1 M( V+ Y0 [* e) |7 \
if(L.length>=L.listsize){
8 j, I4 p3 j  _    newbase=(ElemType *)realloc(L.elem(L.listsize+LISTINCREMENT)*sizeof(ElemType));$ `1 ]9 N2 l7 ]  E, r5 S
    if(!newbase)exit(OVERFLOW); //存储分配失败
- }; U0 x, \, z5 I2 c" n    L.elem=newbase;             //新基址; s5 V1 {, R3 h6 ^5 s3 E
    L.listsize+=LISTINCREMENT;  //增加存储容量, G" x% G$ N  A4 `  Y
}9 [* G3 Y' v2 c1 N% X
q=&(L.elem[i-1]);               //q为插入位置+ q- T$ Z- M  X" R) F: |2 S& t; a; `
for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;
# y+ Z, x7 Z, P7 K3 s6 p                                //插入位置及之后的元素右移9 ?: r' F* ]  O, \
*q=e;          //插入e) u1 i3 E, U- C7 ?6 J) {
++L.Length;     //表长增1% m9 W1 z) K8 p% d1 w
return OK;
6 ~7 i/ n2 X* M  n2 ?}   //ListInsert_Sq  

该用户从未签到

2#
发表于 2016-7-13 17:51 | 只看该作者
感谢楼主分享!!!
0 D2 C9 f$ [4 b- Q& M/ x* x

该用户从未签到

3#
发表于 2016-7-14 14:43 | 只看该作者
资源多,学习不止步,共同进步6 T: O* I1 @6 ~1 m8 g- q/ i+ W
您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

推荐内容上一条 /1 下一条

EDA365公众号

关于我们|手机版|EDA365电子论坛网 ( 粤ICP备18020198号-1 )

GMT+8, 2025-8-1 07:55 , Processed in 0.109375 second(s), 24 queries , Gzip On.

深圳市墨知创新科技有限公司

地址:深圳市南山区科技生态园2栋A座805 电话:19926409050

快速回复 返回顶部 返回列表