Question

关于数据结构（C语言版）的问题

1、已知一个顺序表L，其中的元素递增有序排列，设计一个算法插入一个元素x后保持该顺序表仍递增有序排列。
2、设计一个算法删除单链表L中值为x的结点的直接前驱结点。

只有十分了。。谢谢了

Answer 1

第一题：下面的L.listsize是顺序表在建立的时候分配的总体存储量，INCREMENT是新增加的量，都是实现已经定义好的，EType是元素的类型，到具体的程序中的时候，可以使用typedef定义类型，这里是代指某个类型；具体算法如下：
void inser_order(List &L,EType Elem)
{if(L.length>=L.listsize) //当新增加元素时，表的总体长度大于已经分配的总体大小时，要重新分配表的长度；
{list *newbase;
newbase=(EType *)realloc(L.elem,(L.listsize+INCREMENT)*sizeof(EType));//新分配的表长
if(!newbase) exit(OVERFLOW);//分配不成功；
L.elem=newbase;L.size+=INCREMENT;
}
List *p,*q;
int i=L.length-1;
q=&(L.elem[i]);
while(i>=0)//从表的最后的元素开始比较，寻找合适的插入位置；
{
if(Elem<=L.elem[i]&&Elem>L.elem[i-1]) //插入的数值位于当前值与前面值的中间值时
{
p=&(L.elem[i]);//指向要插入的位置
break;
}
{
if(i==L.length-1) //当插入的值是比最大元素还要大时
{
p=q;//指向最后的位置
break;
}
}
i--;
}
while(q>=p)//从后往前移动各个位置的数，然后找到要插入的位置，插入
{
*(q+1)=*q;
q=q-1;
if(q==p)//找到要插入的位置
{
*(q+1)=*q;
*q=e;//插入元素
++L.length;//表长加1
}
}
}
第二题：
void deletenode(Listnode &L,EType X)
{Listnode *p,*q,*r;//p用来寻找X结点，q用来指向X结点的前驱结点的前驱结点，r指向p所指向结点的前驱结点；
p=L;//初始时，指向头结点；
q=L;
if(p->elem==X)//第一个结点就是所找的X；
{
printf("The first node is X,can't delete its precessor");
exit(1);
}
while(p->next!=NULL)//遍历链表，寻找X的位置
{
if(p->elem==X)//找到X
{
while(q->next!=r)
q=q->next;//寻找X的前驱结点
//删除结点的操作
q->next=p;
r->next=NULL;
free(r);
}
r=p; //r永远指向p所指向结点的前驱结点
p=p->next;//p往后移动
}
}

Answer 2

顺序表和链表都带头结点

（1）
void SeqListInsert(SeqList *L, int num)
{
int i, j = 1;

if (MAXSIZE-1 == L->length)
{
printf("表已满，无法进行插入\n");
return;
}

while (j <= L->length)
{
if (num < data[j])
{
break;
}
else
{
j++;
}
}

L->length++;

for (i=L->length; i>j; i--)
{
data[i] = data[i-1];
}

data[j] = num;
}

（2）
void LinkDelete(LinkNode *head, int num)
{
LinkNode *p = head->next;
LinkNode *q = head;

if (num == p->data)
{
printf("此为第一个结点，无前驱\n");
return;
}

while (NULL != p)
{
if (num == p->next->data)
{
q->next = p->next;
free(p);
return;
}
else
{
p = p->next;
q = q->next;
}
}
}

Answer 3

表指针问题的确是个难点，我当时学时也很头疼。。。

Answer 4

路过……(*^__^*)

追问

诶诶 你刚才有帮我回答么

追答

本人不答题的……

Answer 5

要写代码？

追问

恩。