您好,登錄后才能下訂單哦!
在單鏈表中,又如何實現“插入”和“刪除”操作呢?
插入操作:
假設我們要在線性表的兩個數據元素a和b之間插入一個數據元素x,已知p為其單鏈表存儲結構中指向結點a的指針。為插入數據元素x,首先要生成一個數據域為x的結點,然后插入在單鏈表中。根據插入操作的邏輯定義,還需修改結點a中的指針域,令其指向結點x,而結點x中的指針域應該指向b結點,從而實現3個元素a,b和x之間邏輯關系的變化。
假設s為指向結點x的指針。則上述指針修改用語句描述即為:
s->next=p->next;
p->next=s;
刪除操作:
如果在線性表中刪除元素b時,為在單鏈表中實現元素a,b和c之間邏輯關系的變化,僅需要修改結點a中的指針域即可。假設p為指向結點a的指針,則修改指針的語句為:
p->next=p->next->next;
由以上可知,在已知鏈表中元素插入或刪除的確切位置的情況下,在單鏈表中插入或刪除一個結點時,僅需修改指針為不需要移動元素。
插入函數ListInsert_L:要求是在已知鏈表中的確切位置插入一個結點。所以需要向函數內傳遞已知鏈表L,插入的確切位置i,以及即將插入的結點數據元素e。
ListInsert_L(LinkList &L,int i,ElemType e)
{
//第一步:將鏈表的頭結點的指針域單鏈表存儲結構的指針p
p=L;//&L即為鏈表L的的頭結點地址
j=0;//計數器
//第二步:找到在將在鏈表i處,即要插入新結點的位置。
//方法:先找到鏈表i-1處的結點。此結點的指針域即指向i處結點的指針域
while(p&&j<i-1)
{
p=p->next;//p->next是指向第j+1個數據元素的指針
++j;//
}
//第三步:判斷是否越界已知鏈表
//如果i小于1或者大于表長+1,即越界,則返回錯誤
if(!p||j>i-1)
return ERROP;
//第四步:找到i出結點,新建一個結點(包括數據域和指針域)代表即將插入的結點
//生成新結點
s=(LinkList)malloc(sizeof(LNode));//新結點s
s->data=e;//新結點的數據域賦值為將插入的數據元素e
//因為原來i處結點指針域p保存著指向下一個i+1處結點的指針域。
//要插入新結點,即原來i+1處的結點變為i+2處的幾點,新建結點變為i+1處的結點
//即新建結點指向原來i+1處的結點的指針域,所以s->next=p->next
//因為此時p代表的是i處的結點,p->代表i+1處的結點指針域賦值給新結點指針域
s->next=p->next;
//因為此時p代表的是i處的結點,p->next代表i+1處的結點指針域賦值給新結點指針域
//完成插入操作時,新建結點s變為i+1處的結點。所以p->next指向s,即將s賦值給p->next.
p->next=s;
return OK;
}
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。