帮我看看！四天后就要交了，可我还没有一点头绪！拜托了！可以发到我邮箱里：yyccxx530@yahoo.com.cn
三、 计算机文化课实践要求与实践内容
1. 建立链表，链表的每个结点必须包含三个字符（或字符串）类型的域，四个数值类型的域（其中最后一个数值域表示另外前三个数值域的总和）和一个指针域。
2. 输出链表中的所有结点（以表的形式）。
3. 计算链表中每个结点的最后一个数值域。
4. 在链表中插入若干个结点，是否继续插入依据输入的是“Y”还是“N”，回答“Y”则继续插入。
5. 在链表中删除若干个结点，是否继续删除依据输入的是“Y”还是“N”，回答“Y”则继续删除。
6. 统计链表中结点的个数。
7. 把链表中的结点转换成数组存放。
8. 对数组按数值型域进行排序（升序）。
9. 对数组查找给定的关键字值（要求用顺序查找和折半查找，其中折半查找对排序后的数组进行查找）。
建议用菜单组织以上各种操作。
没有结果，是不是还少了什么语句，我看不出来，帮我找找啊
谢谢了！
#include <string.h>
#include <stdio.h>
#include <iostream.h>
#include <malloc.h>
#define N 100
typedef struct node
{ char c1[50];
int i1,i2,i3,i4;
struct node *next;
}lnode,*linklist;

linklist creat_linklist() //头查法创建单链表 1
{ linklist L=NULL;
lnode *s;
char c4[50],c5[20]="end";
cout<<"请输入一个字符串(输入'end'结束)"<<endl;
gets(c4);
while(strcmp(c4,c5)!=0)
{ if((s=(lnode *)malloc(sizeof(lnode)))==NULL)
{cout<<"不能分配内存空间！"<<endl;
return NULL;}
strcpy(s->c1,c4);
// cout<<"请输入两个字符串"<<endl;
// cin>>s->c2>>s->c3;
cout<<"请输入三个整形数"<<endl;
cin>>s->i1>>s->i2>>s->i3;
s->i4=s->i1+s->i2+s->i3;
s->next=L;L=s;
cout<<"请输入一个字符串(输入'end'结束)"<<endl;
gets(c4);
}
return L;
}

void print(linklist L) //输出链表 2
{ while(L->next!=NULL)
{ cout<<"姓名 语文 数学 英语 总成绩"<<endl;
cout<<L->c1 <<L->i1 << L->i2 << L->i3 << L->i4<<endl;
cout<<"->"<<endl;
L=L->next;}
cout<<"姓名 语文 数学 英语 总成绩"<<endl;
cout<<L->c1 <<L->i1<<L->i2 <<L->i3<< L->i4<<endl;
}

int length_linklist(linklist L) //求表长 3
{ lnode *p=L;
int j;
if(p==NULL) return 0;
j=1;
while(p->next!=NULL)
{p=p->next;j++;}
return j;
}

lnode *charlocate_linklist(linklist L) //按值查找中，查找字符串
{ char x1[20];
lnode *p;
if((p=(lnode *)malloc(sizeof(lnode)))==NULL)
{cout<<"不能分配内存空间！"<<endl;
return NULL;}
cout<<"请输入要查找的学生姓名:"<<endl;
gets(x1);
p=L;
while((p!=NULL)&&(strcmp(p->c1,x1)!=0))
p=p->next;
return p;
}

//lnode *intlocat_linklist(linklist l,int x) //按值查找中，查找数字
//{ lnode *p;
// if((p=(lnode *)malloc(sizeof(lnode)))==NULL)
// {cout<<"不能分配内存空间！"<<endl;
// return NULL;}
// p=l;
// while((p!=NULL)&&(p->i1!=x)&&(p->i2!=x)&&(p->i3!=x)&&(p->i4!=x))
// p=p->next;
// return p;
//}

//lnode *locate_linklist(linklist l) //按值查找
//{ cout<<"1.查找字符串"<<endl;
// cout<<"2.查找数字"<<endl;
// int x;
// cin>>x;
// switch(x)
// { case 1:cout<<"请输入要查找的字符串:"<<endl;
// char x1[20];gets(x1);return charlocate_linklist(l,x1);break;
// case 2:cout<<"请输入要查找的数字:"<<endl;
// int x2;cin>>x2;return intlocat_linklist(l,x2);break;
// default: return NULL;break;
//}
//}

linklist insert_linklist(linklist L) //按值查找插入操作 4
{ int x;
lnode *p,*q,*h;
cout<<"请问要在哪个元素的前面（或后面）插（学生姓名）:"<<endl;
p=charlocate_linklist(L);
if(p==NULL)
{cout<<"该元素不存在！"<<endl;cout<<"插入失败!"<<endl;return L;}
else{if((h=(lnode *)malloc(sizeof(lnode)))==NULL)
{cout<<"不能分配内存空间！"<<endl;
return L;}
cout<<"请输入要插入的元素的值"<<endl;
cout<<"请输入学生姓名"<<endl;
cin>>h->c1;
cout<<"请输入三科成绩"<<endl;
cin>>h->i1>>h->i2>>h->i3;
h->i4=h->i1+h->i2+h->i3;
cout<<"请问是要在之前查找到的元素的前面插入还是后面插入，前插请选1，后插请选2:"<<endl;
cin>>x;
switch(x)
{case 1:if((q=(lnode *)malloc(sizeof(lnode)))==NULL)
{cout<<"不能分配内存空间！"<<endl;
return L;break;}
if(p==L)
{h->next=p;L=h;cout<<"插入成功!"<<endl;return L;break;}
else
{for(q=L;q->next!=p;q=q->next);
h->next=q->next;q->next=h;cout<<"前插成功!"<<endl;return L;break;}
case 2:h->next=p->next;p->next=h;cout<<"后插成功!";return L;break;
default:return L; break;}
}
}

linklist del_linklist(linklist L) //按值查找删除操作 5
{ lnode *p,*q;
cout<<"请输入要删除哪个学生记录:"<<endl;
p=charlocate_linklist(L);
if(p==NULL)
{cout<<"该元素不存在!"<<endl;cout<<"删除失败!"<<endl;return L;}
else{if(p==L)
{L=L->next;cout<<"删除成功!"<<endl;return L;}
else {if((q=(lnode *)malloc(sizeof(lnode)))==NULL)
{cout<<"不能分配内存空间！"<<endl;
return L;}
else {for(q=L;q->next!=p;q=q->next)
q->next=p->next;
cout<<"删除成功!"<<endl;
return L;}
}
}
}
void display_i4(linklist L) //链表中每个结点的最后一个数值域 6
{ while(L->next!=NULL)
{cout<<L->i4<<endl;
L=L->next;}
cout<<L->i4<<endl;
}

int is_search(linklist L) //数字的顺序查找 7
{ lnode *p;
int kx,r[N],i=0,j;
cout<<"请输入您要查找的数字:"<<endl;
cin>>kx;
r[0]=kx;
if((p=(lnode *)malloc(sizeof(lnode)))==NULL)
{cout<<"不能分配内存空间！"<<endl;
return NULL;}
p=L;
while(p!=NULL)
{r[4*i+1]=p->i1;
r[4*i+2]=p->i2;
r[4*i+3]=p->i3;
r[4*i+4]=p->i4;
p=p->next;
i++;}
for(j=4*i;r[j]!=kx;j--);
for(int z=0;z<=4*i;z++)
cout<<r[z]<<endl;
cout<<"该元素的位置为:"<<endl;
return j;
}

int cs_search(linklist L) //字符串的顺序查找 7
{ lnode *p;
char kx[20],r[N][N];
int i=1,j;
cout<<"请输入您要查找的字符串:"<<endl;
gets(kx);
strcpy(r[0],kx);
if((p=(lnode *)malloc(sizeof(lnode)))==NULL)
{cout<<"不能分配内存空间！"<<endl;
return NULL;}
p=L;
while(p!=NULL)
{strcpy(r[i],p->c1);
//strcpy(r[3*i+2],p->c2);
//strcpy(r[3*i+3],p->c3);
p=p->next;
i++;}
for(j=i-1;strcmp(r[j],kx)!=0;j--);
for(int z=0;z<=3*i;z++)
cout<<r[z]<<endl;
cout<<"该元素的位置为:"<<endl;
return j;
}

int s_search(linklist l) //顺序查找的选择 7
{ cout<<"1.查找字符串"<<endl;
cout<<"2.查找数字"<<endl;
int x;
cin>>x;
switch(x)
{ case 1:return cs_search(l);break;
case 2:return is_search(l);break;
default: return NULL;break;
}
}

void bublesort(linklist L) //冒泡排序法升序排序 8
{ lnode *p;
int r[N],i=1,temp;
if((p=(lnode *)malloc(sizeof(lnode)))==NULL)
{cout<<"不能分配内存空间！"<<endl;}
else {p=L;
while(p!=NULL)
{//r[4*i+0]=p->i1;
//r[4*i+1]=p->i2;
//r[4*i+2]=p->i3;
r[i]=p->i4;
p=p->next;
i++;}
for(int x=i-2;x>0;x--)
for(int y=0;y<i-2;y++)
if(r[y+1]<r[y])
{temp=r[y+1];
r[y+1]=r[y];
r[y]=temp;}
cout<<"排序后的数组为:"<<endl;
for(int z=0;z<i-1;z++)
cout<<r[z]<<endl;}
}

int binary_search(linklist L) //有序表的折半查找 9
{ //lnode *p;
int i=1;
char r[N];
void bublesort(linklist L);
//if((p=(lnode *)malloc(sizeof(lnode)))==NULL)
// {cout<<"不能分配内存空间！"<<endl;
// return NULL;}
// p=L;
// while(p!=NULL)
// {//r[4*i+1]=p->i1;
// //r[4*i+2]=p->i2;
// //r[4*i+3]=p->i3;
// r[i]=p->c1;
// p=p->next;
// i++;}
// for(int x=i-2;x>0;x--)
// for(int y=1;y<i-1;y++)
// if(r[y+1]<r[y])
// {temp=r[y+1];
// r[y+1]=r[y];
// r[y]=temp;}
int low=1,mid,high=4*i,flag=0,kx;
cout<<"请输入要查找的数字:"<<endl;
cin>>kx;
while(low<=high)
{ mid=(low+high)/2;
if(kx<r[mid]) high=mid-1;
else if(kx>r[mid]) low=mid+1;
else {flag=mid;break;}
}
cout<<"该元素在数组中的位置为:"<<endl;
return flag;
}

void main()
{ linklist a;
int z;
char s;
do
{cout<<"1.头查法创建单链表"<<endl;
cout<<"2.打印链表"<<endl;
cout<<"3.求表长"<<endl;
cout<<"4.插入操作"<<endl;
cout<<"5.删除操作"<<endl;
cout<<"6.链表中每个结点的最后一个数值域"<<endl;
cout<<"7.顺序查找"<<endl;
cout<<"8.对数组按数值型域进行升序排序"<<endl;
cout<<"9.对有序表进行折半查找"<<endl;
cout<<"0.退出"<<endl;
cin>>z;
switch(z)
{case 1:a=creat_linklist();break;
case 2:a=creat_linklist();break; print(a);break;
case 3:cout<<length_linklist(a)<<endl;break;
case 4:do {a=insert_linklist(a);cout<<"是否继续插入元素?(Y/N)"<<endl;
cin>>s;}while(s=='Y');break;
case 5:do {a=del_linklist(a);cout<<"是否继续删除元素?(Y/N)"<<endl;
cin>>s;}while(s=='Y');break;
case 6:display_i4(a);break;
case 7:cout<<s_search(a)<<endl;break;
case 8:bublesort(a);break;
case 9:cout<<binary_search(a)<<endl;break;
default: break;}
}while(z);
}

[此贴子已经被作者于2006-1-11 18:30:22编辑过]

给初学者的参考算法：
算法设计题部分
1、试编写一个求已知单链表的数据域的平均值的函数（数据域数据类型为整
型）。
解答：#include "stdio.h"
#include "malloc.h"
typedef struct node
{int data;
struct node *link;
}NODE;
int aver(NODE *head)
{int i=0,sum=0,ave; NODE *p;
p=head;
while(p!=NULL)
{p=p->link;++i;
sum=sum+p->data;}
ave=sum/i;
return (ave);}
2、已知带有头结点的循环链表中头指针为head,试写出删除并释放数据域值
为x的所有结点的c函数。
解答：#include "stdio.h"
#include "malloc.h"
typedef struct node
{
int data; /* 假设数据域为整型 */
struct node *link;
}NODE;

void del_link(NODE *head,int x) /* 删除数据域为x的结点*/
{
NODE *p,*q,*s;
p=head;
q=head->link;
while(q!=head)
{
if(q->data==x)
{
p->link=q->link;
s=q;
q=q->link;
free(s);
}
else
{
p=q;
q=q->link;
}
}
}
3、某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环
链表，每个结点有价格、数量和链指针三个域。现出库（销售）m台价格
为h的电视机，试编写算法修改原链表。
解答：
void del(NODE *head,float price,int num)
{
NODE *p,*q,*s;
p=head;q=head->next;
while(q->price<price&&q!=head)
{
p=q;
q=q->next;
}
if(q->price==price)
q->num=q->num-num;
else
printf("无此产品");
if(q->num==0)
{
p->next=q->next;
free(q);
}
}
4、某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环
链表，每个结点有价格、数量和链指针三个域。现新到m台价格为h的电视机，试编写算法修改原链表。
#include "stdio.h"
#include "malloc.h"
typedef struct node
{
float price;
int num;
struct node *next;
}NODE;
void ins(NODE *head,float price,int num)
{
NODE *p,*q,*s;
p=head;q=head->next;
while(q->price<price&&q!=head)
{
p=q;
q=q->next;
}
if(q->price==price)
q->num=q->num+num;
else
{
s=(NODE *)malloc(sizeof(NODE));
s->price=price;
s->num=num;
s->next=p->next;
p->next=s;
}
}
算法设计题部分
1、线性表中的元素值按递增有序排列，针对顺序表和循环链表两种不同的存储方式，分别编写C函数删除线性表中值介于a与b（a≤b）之间的元素。
顺序表：
算法思想：从0开始扫描线性表，用k记录下元素值在a与b之间的元素个数，对于不满足该条件的元素，前移k个位置，最后修改线性表的长度。
void del（elemtype list[]，int *n，elemtype a，elemtype b）
{
int i=0，k=0；
while（i<n)
{
if(list[i]>=a&&list[i]<=b) k++;
else
list[i-k]=list[i];
i++;
}
*n=*n-k; /* 修改线性表的长度*/
}
循环链表:
void del(NODE *head,elemtype a,elemtype b)
{
NODE　*p,*q;
p= head;q=p->link; /* 假设循环链表带有头结点 */
while(q!=head && q->data<a)
{
p=q;
q=q->link;
}
while(q!=head && q->data<b)
{
r=q;
q=q->link;
free(r);
}
if(p!=q)
p->link=q;
}
算法设计题部分
设A=(a0,a1,a2,...,an-1),B=(b0,b1,b2,...,bm-1)是两个给定的线性表,它们的结点个数分别是n和m,且结点值均是整数。
若n=m，且 ai= bi （0≤i<n ），则A=B；
若n<m ，且ai=bi （0≤i<n ），则A<B；
若存在一个j， j<m ，j<n ，且ai=bi （0≤i<j ）， 若aj<bj，则A<B，否则 A>B。
试编写一个比较A和B的C函数，该函数返回 -1或 0或 1，分别表示 A<B或 A=B或 A>B。
#define MAXSIZE 100
int listA[MAXSIZE],listB[MAXSIZE];
int n,m;
int compare(int a[],int b[])
{
int i=0;
while(a[i]==b[i]&&i<n&&i<m)
i++;
if(n==m&&i==n) return(0);
if(n<m&&i==n) return(-1);
if(n>m&&i==m) return(1);
if(i<n&&i<m)
if(a[i]<b[i]) return(-1);
else if(a[i]>b[i]) return(1);
}

算法设计题部分
试编写算法,删除双向循环链表中第k个结点。
void del(DUNODE　**head,int i)
{
DUNODE *p;
if(i==0)
{
*head=*head->next;
*head->prior=NULL;
return(0);
}　
else
{for(j=0;j<i&&p!=NULL;j++)
p=p->next;
if(p==NULL||j>i) return(1);
p->prior->next=p->next;
p->next->prior=p->proir;
free(p);
return(0);
}
算法设计题部分
线性表由前后两部分性质不同的元素组成(a0,a1,...,an-1,b0,b1,...,bm-1),m和n为两部分元素的个数,若线性表分别采用数组和链表两种方式存储,编写算法将两部分元素换位成(b0,b1,...,bm-1,a0,a1,...,an-1),分析两种存储方式下算法的时间和空间复杂度。
顺序存储:
void convert(elemtype list[],int l,int h) /* 将数组中第l个到第h个元素逆置*/
{
int i;
elemtype temp;
for(i=h;i<=(l+h)/2;i++)
{
temp=list[i];
list[i]=list[l+h-i];
list[l+h-i]=temp;
}
}
void exchange(elemtype list[],int n,int m);
{
convert(list,0,n+m-1);
convert(list,0,m-1);
convert(list,m,n+m-1);
}
该算法的时间复杂度为O(n+m),空间复杂度为O(1)
链接存储:(不带头结点的单链表)
typedef struct node
{
elemtype data;
struct node *link;
}NODE;
void convert(NODE **head,int n,int m)
{
NODE *p,*q,*r;
int i;
p=*head;
q=*head;
for(i=0;i<n-1;i++)
q=q->link; /*q指向an-1结点 */
r=q->link;
q->link=NULL;
while(r->link!=NULL)
r=r->link; /*r指向最后一个bm-1结点 */
*head=q;
r->link=p;
}
该算法的时间复杂度为O(n+m),但比顺序存储节省时间(不需要移动元素,只需改变指针),空间复杂度为O(1)
算法设计题部分
用循环链表作线性表(a0,a1,...,an-1)和（b0,b1,...,bm-1）的存储结构,头指针分别为ah和bh，设计C函数，把两个线性表合并成形如（a0,b0,a1,b1,…）的线性表，要求不开辟新的动态空间,利用原来循环链表的结点完成合并
操作,结构仍为循环链表,头指针为head,并分析算法的时间复杂度。
typedef struct node
{
elemtype data;
struct node *link;
}NODE;
NODE　*union(NODE　*ah,NODE *bh)
{
NODE　*a,*b,*head,*r,*q;
head=ah;
a=ah;
b=bh;
while(a->link!=ah&&b->link!=bh)
{
r=a->link;
q=b->link;
a->link=b;
b->link=r;
a=r;
b=q;
}
if(a->link==ah) /*a的结点个数小于等于b的结点个数 */
{
a->link=b;
while(b->link!=bh)
b=b->link;
b->link=head;
}
if(b->link==bh) /*b的结点个数小于a的结点个数 */
{
r=a->link;
a->link=b;
b->link=r;
}
return(head);
}
该算法的时间复杂度为O(n+m),其中n和m为两个循环链表的结点个数.

算法设计题部分
试写出将一个线性表分解为两个带有头结点的循环链表，并将两个循环链表的长度放在各自的头结点的数据域中的C函数。其中,线性表中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中。
typedef struct node
{
elemtype data;
struct node *link;
}NODE;
void analyze(NODE *a）
{
NODE　*rh，*qh，*r,*q,*p；
int i=0，j=0；/*i为序号是奇数的结点个数 j为序号是偶数的结点个数 */
p=a；
rh=（NODE *）malloc（sizeof（NODE））；/*rh为序号是奇数的链表头指针 */
qh=(NODE *)malloc(sizeof(NODE)); /*qh为序号是偶数的链表头指针 */
r=rh;
q=qh;
while(p!=NULL)
{
r->link=p;
r=p;
i++;
p=p->link;
if(p!=NULL)
{
q->link=p;
q=p;
j++;
p=p->link;
}
}
rh->data=i;
r->link=rh;
qh->data=j;
q->link=qh;
}

算法设计题部分
试写出把线性链表改为循环链表的C函数。
typedef struct node
{
elemtype data;
struct node *link;
}NODE;
void change(NODE　*head)
{
NODE　*p;
p=head;
if(head!=NULL)
{
while(p->link!=NULL)
p=p->link;
p->link=head;
}
}
算法设计题部分
己知非空线性链表中x结点的直接前驱结点为y,试写出删除x结点的C函数。
typedef struct node
{
elemtype data;
struct node *link;
}NODE;
void del(NODE *x,NODE *y)
{
NODE *p,*q;
elemtype d1;
p=y;
q=x;
while(q->next!=NULL) /* 把后一个结点数据域前移到前一个结点*/
{
p->data=q->data;
q=q->link;
p=q;
}
p->link=NULL; /* 删除最后一个结点*/
free(q);
}