线性表编程题

#include \"stdafx.h\" #include using namespace std; typedef int ElemType; struct SqList { ElemType *elem; int listsize; int length; };

void InputData(SqList &LA);

void MergeList_Sq(SqList LA,SqList LB,SqList &LC); void print(SqList LC); void main() { SqList LA,LB,LC; LA.elem=new ElemType[100]; LA.length=0; LA.listsize=100; LB.elem=new ElemType[100]; LB.length=0; LB.listsize=100; InputData(LA); InputData(LB); MergeList_Sq(LA,LB,LC); print(LC); }

void InputData(SqList &LA) { cout<<\"请按升序输入一系列整数，用空格隔开，以-9999结尾：\"; int temp; for(int i=0;;i++) { cin>>temp;

if(temp!=-9999) { LA.elem[i]=temp; LA.length++; } else break; } }

void print(SqList LC) { for(int i=0;ivoid MergeList_Sq(SqList LA,SqList LB,SqList &LC) {///LA、LB中元素原来按非递减顺序存储 /////要求合并后的LC也按照非递减序存储 int i,j,k; i=j=k=0;

//下面生成线性表LC

LC.length=LA.length+LB.length; LC.listsize=LA.length+LB.length;

LC.elem=new ElemType[LC.listsize];

while(i<=LA.length-1 && j<=LB.length-1)

{//当LA、LB同时不为空时，进行下面操作 ElemType pa=LA.elem[i];//取LA的第i个元素 ElemType pb=LB.elem[j];//取LB的第j个元素 if(pa<=pb) {//如果pa<=pb LC.elem[k]=pa;//pa插入LC尾部 k++;i++;//LC、LA下标后移 } else { LC.elem[k]=pb; k++;j++; } }

while(i<=LA.length-1)

{//如果LA中还有元素，则所有元素全部插入LC尾部 ElemType pa=LA.elem[i]; LC.elem[k]=pa;

}

k++;i++; }

while(j<=LB.length-1)

{//如果LB中还有元素，则所有元素全部插入LC尾部 ElemType pb=LB.elem[j]; LC.elem[k]=pb; k++;j++; }

2.构造一个链式存储的线性表（当输入9999时结束构造过程），然后输出该线性链表，并统计该线性链表的长度。 #include \"stdafx.h\" #include using namespace std;

struct LinkNode{ int data; struct LinkNode *next; };

void print(LinkNode *L)

{//将链表L中的数据输出到屏幕上，其中L指向头结点 LinkNode *p; //定义一个指针变量 p=L->next; //让p指向链表L的第一个数据 while(p!=0) { cout<data<<\"\"; //输出数据到屏幕上 p=p->next; //指针后移 } cout<void Insert_head(LinkNode *&H,int x)

{//在以H为头结点的单链表的头结点后面插入一个数据x LinkNode *t; //定义指针 t=new LinkNode; //申请新结点空间

t->data=x; //向新结点中写入数据 t->next=H->next; //把单链表的第一个结点的地址写入新结点中 H->next=t; //让头结点的next指针指向新结点 }

int Length_LinkList(LinkNode *L) {//返回单链表L的长度 LinkNode *p;//定义一个指针变量

int len=0;//定义一个计数器，用于累计结点个数 p=L->next ;//让p指向链表的第一个结点 while(p!=0) {

len++;//计数器累计1 p=p->next;//p指针后移，即指向链表当前结点的后继结点 } return len; }

int main(int argc, char* argv[]) { LinkNode *H; //定义链表指针 H=new LinkNode; //申请空间

H->data=-1; //为成员变量数据赋值 H->next=0; //为成员变量指针赋值 int x,count; cout<<\"enter linklist elems:\"<>x; if(x==9999) break; else {

Insert_head(H,x); //构造一个线性链表 } }

cout<<\"The linklist elems is:\"<count=Length_LinkList(H); //统计元素个数

cout<<\"The linklist elems amount is:\"<3.构造一个链式存储的线性表（当输入9999时结束构造过程），在第i个位置插入新元素x，并输出显示线性链表。 #include \"stdafx.h\" #include using namespace std;

struct LinkNode{ int data; struct LinkNode *next; };

void print(LinkNode *L)

{//将链表L中的数据输出到屏幕上，其中L指向头结点 LinkNode *p; //定义一个指针变量 p=L->next; //让p指向链表L的第一个数据 while(p!=0) { cout<data<<\"\"; //输出数据到屏幕上 p=p->next; //指针后移 } cout<int Length_LinkList(LinkNode *L)

{//返回单链表L的长度 LinkNode *p;//定义一个指针变量 int len=0;//定义一个计数器，用于累计结点个数 p=L->next ;//让p指向链表的第一个结点 while(p!=0) { len++;//计数器累计1 p=p->next;//p指针后移，即指向链表当前结点的后继结点 } return len; }

LinkNode* Address_LinkList(LinkNode *L, int i)

{//单链表中寻找第i个元素，返回指向第i个元素结点的指针 if(i<1 || i>Length_LinkList(L))//如果i位置不合法，返回空指针 { printf(\"error!exit!\\n\"); exit(1); }

LinkNode *p;//定义指针变量 int j=0;//定义计数器，用于累计经过的结点个数 p=L;//让p指向头结点 while(jnext;//指针后移 j++;//计数器累计 } return p; }

void Insert_head(LinkNode *&H,int x)

{//在以H为头结点的单链表的头结点后面插入一个数据x LinkNode *t; //定义指针 t=new LinkNode; //申请新结点空间 t->data=x; //向新结点中写入数据

t->next=H->next; //把单链表的第一个结点的地址写入新结点中 H->next=t; //让头结点的next指针指向新结点 }

void ListInsert_LinkList(LinkNode *&L, int i, int x) {//在单链表L的第i个位置插入数据x LinkNode *p;//定义一个指针变量 if(i==1) p=L; //让p指向头结点 else

p=Address_LinkList(L,i-1);//让p指向第i-1个结点 Insert_head(p,x); //将x插入假设以p结点为头结点的链表中 }

int main(int argc, char* argv[]) {

LinkNode *H; //定义链表指针 int i,x;

H=new LinkNode; //申请空间

H->data=-1; //为成员变量数据赋值 H->next=0; //为成员变量指针赋值 cout<<\"enter linklist elems:\"<>x; if(x==9999) break; else { Insert_head(H,x); //构造一个线性链表 } }

cout<<\"The linklist elems:\"<cout<<\"The linklist inserted position is:\"<>i; cout<<\"The linklist inserted elem is:\"<>x; ListInsert_LinkList(H, i, x); //在第i个位置插入新元素x cout<<\"The new linklist elems:\"<