#include
#define List_Init_Size 10 #define ListIncrement 10 typedef int Status;//状态类型 typedef struct{
int num;//专家号，不重复，可用于查找专家 char name[30];//专家姓名，可能重复
}ElemType; //元素类型-----专家信息数据类型---------特别关注“数据元素”-------------// typedef ElemType ET; typedef struct Lnode{ ElemType data; struct Lnode *next; }LNode,*LinkList;
void Invert_L(LinkList L); void Delete_L(LinkList L);
Status Merge_L(LinkList La,LinkList Lb,LinkList &Lc);
Status InitList_L(LinkList &L);//创建长度为0的空链表 int ListLength_L(LinkList L); //返回链表长度
Status GetElem_L(LinkList L, int i,ET &e); //提取链表中的一个元素，赋值给e
Status ListInsert_L(LinkList L , int i , ET e); //将值为e的元素插入链表（位置为i） Status ListDelete_L(LinkList L , int i , ET &e); //删除链表i位置的元素，并赋值给e Status PriorElem_L(LinkList L , ET e , ET &pre_e);//将e的前驱元素返回给pre_e void creatList(LinkList &L,int n);//创建一个长度为n的链表，并将所有元素赋值 void printList(LinkList L);//打印链表中所有元素的num值和链表的长度
void main() { Status s; LinkList L1,L2,L3; creatList(L1,0); creatList(L2,10); printList(L1); printList(L2); s = Merge_L(L1,L2,L3); printList(L3);
printList(L1); printList(L2); }
/********************************************提交函数开始***************************************/
//（1） （30分）
//功能：实现将链表L中数据逆置。（例如：原表中数据为1, 2, 3, 4 ,5, 6。逆置处理后表中数据为6, 5, 4, 3, 2, 1。） void Invert_L(LinkList L) { int length = 0; LinkList p = L; while (p->next) { length++; p = p->next; } if(length) { ElemType *et = (ElemType *)malloc(length * sizeof(ElemType)); p = L; for(int y = 0; y < length; y++) { et[y] = p->next->data; p = p->next; } p = L; for(int x = length - 1; x >= 0; x--) { p->next->data = et[x]; p = p->next; } } }
//（2）（30）
//功能：已知单链表中的元素以专家号值递增有序排列。试写一高效的算法，
//删除表中所有专家号值（data.num）相同的多余元素（使得运算后的表中无重复信息），并分析你的算法的时间复杂度。 void Delete_L(LinkList L) { LinkList p1,p2;
int flag; while(L->next->next) { flag = L->next->data.num; L = L->next; while(flag == L->next->data.num) { p1 = L->next->next; p2 = L->next; L->next = p1; free(p2); } } }
//（3）（40分）
//功能：已知两个非递减有序单链表La、Lb，编写程序实现将La、Lb合并成一个非递减有序单链表Lc，同时置La，Lb为空表。
//返回值：成功返回Ok；否则，返回Error。 //注：Lc的值不可用，必须初始化
Status Merge_L(LinkList La,LinkList Lb,LinkList &Lc) { LinkList p1 = La; LinkList p2 = Lb; ElemType* et; ElemType e; int length1 = 0,length2 = 0; while(p1->next) { p1 = p1->next; length1++; } while(p2->next) { p2 = p2->next; length2++; } et = (ElemType *)malloc((length1 + length2) * sizeof(ElemType)); while(!et) { et = (ElemType *)malloc((length1 + length2) * sizeof(ElemType)); } p1 = La;
p2 = Lb; int x = 0;
while(p1->next) { et[x] = p1->next->data; p1 = p1->next; x++; }
while(p2->next) { et[x] = p2->next->data; p2 = p2->next; x++; } int y;
for(x = 1; x < length1 + length2; x++) { for(y = 0;y < (length1 + length2 - x); y++) { if (et[y].num > et[y + 1].num) { e = et[y]; et[y] = et[y + 1]; et[y + 1] = e; } } }
Lc = (LinkList)malloc(sizeof(LNode)); if(!Lc) { return Error; }
p2 = Lc;
for(y = 0; y < length1 + length2; y++) { p1 = (LinkList)malloc(sizeof(LNode)); p2->next = p1; p2 = p1; p2->data = et[y]; }
p2->next = NULL; if(length1 > 0)
{ p1 = La->next->next; p2 = La->next; La->next = NULL; while(!p2) { free(p2); p2 = p1; if(p1) { p1 = p1->next; } } } if(length2 > 0) { p1 = Lb->next->next; p2 = Lb->next; Lb->next = NULL; while(!p2) { free(p2); p2 = p1; if(p1) { p1 = p1->next; } } } return Ok; }
/***********************************************************************************/
void creatList(LinkList &L,int n) { LinkList p1,p2;
提交函数结束