Question

跪求数据结构（c语言版）的几个问题解答

跪求高手写出算法和完整的c程序，先谢谢啦
实验一
表单链的练习
建立一单链表（顺建，且该单链表中各个结点已NUM递增有序）
结点结构（下同）：

NUM（学号） SCORE（成绩） NEXT（指针域）
在该单链表中删除一指定结点；
将一个已知结点插入到该单链表中；
将上述函数组织在一个程序中。

实验二
求两个串的最长公共子串
采用顺序存储方式存储输入的两个串，然后输出它们的最长公共子串。

Answer 1

实验一
单链表有一个头节点h e a d，指向链表在内存的首地址。链表中的每一个节点的数据类型为结构体类型，节点有两个成员：整型成员（实际需要保存的数据）和指向下一个结构体类型节点的指针即下一个节点的地址（事实上，此单链表是用于存放整型数据的动态数组）。链表按此结构对各节点的访问需从链表的头找起，后续节点的地址由当前节点给出。无论在表中访问那一个节点，都需要从链表的头开始，顺序向后查找。链表的尾节点由于无后续节点，其指针域为空，写作为N U L L。
删除运算是将表的第i个结点删去。
具体步骤：
　（1）找到要删除结点ai的存储位置p（因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中）
　（2）令p-＞next指向ai的直接后继结点（即把ai从链上摘下）
　（3）释放结点ai的空间，将其归还给"存储池"。

插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。
具体步骤：
　（1）找到ai-1存储位置p
　（2）生成一个数据域为x的新结点*s
　（3）令结点*p的指针域指向新结点
　（4）新结点的指针域指向结点ai。
#include<stdio.h>
typedef int numtype;
typedef float scoretype;
typedef struct node
{numtype num;<br/>scoretype score;<br/>struct node *next;<br/>}linklist;
int n;

//创建单链表
linklist *creat()
{
linklist *head,*p1,*p2;
n=0;
p1=p2=(linklist*)malloc(sizeof(linklist));
printf("请输入第1个学号:\n"); //单链表内容,学号和成绩
scanf("%d",&p1->num);
printf("请输入第1个成绩:\n");
scanf("%f",&p1->score);
head=NULL;
while(1)
{n=n+1;<br/>if(n==1)<br/>head=p1;<br/>else p2->next=p1;<br/>p2=p1;<br/>p1=(linklist*)malloc(sizeof(linklist));<br/>printf("请输入第%d个学号:\n",n+1);<br/>scanf("%d",&p1->num);<br/>if(p1->num == 0) //这里是终止输入的符号，也就是学号输入0，那么就停止输入。你也可以设置为其它的符号<br/> break;<br/>printf("请输入第%d个成绩:\n",n+1);<br/>scanf("%f",&p1->score);<br/>}
p2->next=NULL;
return head;
}

//单链表的插入
linklist *insert(linklist *head,linklist *stud)
{ linklist *p1,*p2,*p0;
p1=head;
p0=stud;
if(head==NULL)
{ head=p0;p0->next=NULL;}
else
{ while((p0->score>=p1->score)&&(p1->next!=NULL))
{ p2=p1;p1=p1->next; }
if(p0->score<p1->score)
{ if(head==p1) head =p0;
else p2->next=p0;
p0->next=p1;}
else
{ p1->next=p0;
p0->next=NULL;
}
}
return head;
}

//单链表的删除
linklist *del(linklist *head,float dscore)
{
linklist *p1,*p2;
if(head==NULL)
{printf("\n list is NULL!");<br/> return (head);<br/> }
else
{
p1=head;
while((dscore!=p1->score)&&(p1->next!=NULL))
{
p2=p1;
p1=p1->next;
}
if(dscore == p1->score)
{
if(p1==head)
head=head->next;
else
p2->next=p1->next;
free(p1);
printf("已删除:%.2f\n",dscore);
}
else
printf("%.2f 没有在链表中找到!\n",dscore);
}
return head;
}

//输出单链表
void display(linklist *r)
{linklist *t;<br/>t=(linklist*)malloc(sizeof(linklist));<br/>t=r;<br/>printf("\n 单链表显示 :\n学号\t成绩\n");<br/>if(t==NULL)<br/>printf("链表为空。");<br/>else<br/>while(t!=NULL)<br/>{<br/>printf("%d\t",t->num);<br/>printf("%.2f\n ",t->score);<br/>t=t->next;<br/>}
printf("\n");
}

//单链表的插入与删除
int main()
{
float s;
linklist *q,*p;
p=(linklist*)malloc(sizeof(linklist));
q=creat();
display(q);
printf("请输入要删除的结点对应的成绩:");
scanf("%f",&s);
q=del(q,s);
display(q);
printf("请输入要插入的学号和成绩:\n");
printf("学号：");
scanf("%d",&p->num);
printf("成绩:");
scanf("%f",&p->score);
q=insert(q,p);
display(q);
return 0;
}

Answer 2

实验一：（新手初试牛刀 如有缺点请指教）
#include <stdlib.h>
#include <stdio.h>
struct student
{
char name[20];
int number;
double score;
student * next;
};
bool empty(student * head);
void print(student *head)
{
student * p=head->next;
if(empty(head))
{
printf("\n空链表\n");
}
else
{
printf("\n姓名\t学号\t成绩");
while(p)
{
printf("\n%s\t%d\t%d\n",p->name,p->number,p->score);
p=p->next;
}
}
}
bool empty(student * head)
{
if(head->next==NULL)
return true;
else
return false;
}
void create(student * head)
{
student *q=(student *) malloc (sizeof(student));
student *p=head;
printf("\n请输入姓名: ");
scanf("%s",q->name);
printf("学号=");
scanf("%d",&q->number);
printf("成绩=");
scanf("%d",&q->score);
q->next=NULL;
while(p->next)p=p->next;
p->next=q;
print(head);
}
void Delete(student *head,int number)
{
student *p=head;
student *q=p;
while(q->next)
{ q=q->next;
if(q->number==number)
{
if(q->next==NULL)
{
p->next=NULL;
}
else
{
p->next=q->next;
}
}
p=q;
}
print(head);
}
void main()
{
student * head=(student *) malloc (sizeof(student));
int i,n;
head->next=NULL;
printf("请选择 1.插入 2.删除 0.退出\n");
scanf("%d",&i);
while(i)
{
if(i==1)
{
create(head);
}
else if(i==2)
{
printf("\n请输入要删除的学号：");
scanf("%d",&n);
Delete(head,n);
}
printf("请选择 1.插入 2.删除 0.退出\n");
scanf("%d",&i);
}

}

Answer 3

1.语言简洁,紧凑,使用方便,灵活.
2.运算符丰富.
3.数据类型丰富,具有现代语言的各种数据结构.
4.具有结构化的控制语句.
5.语法限制不太严格,程序设计自由度大.
6.C语言允许直接访问物理地址,能进行位操作,能实现汇编语言的大部分功能,可以直接对硬件进行操作.
7.生成目标代码质量高,程序执行效率高.
8.用C语言编写的程序可移植性好.