软件基础实验报告(3)

}

cin>>p->a[i]; p->n=(p->n)+1; }

for( i=0;i<10;i++) {

cout<a[i]<

cout<<\

运行结果如图

2、单链表的生成、插入、和删除运算： #include #include void main() {

typedef struct node {

int data;

struct node * next; }listnode;

typedef listnode *linklist; listnode * p; linklist head,q;

head=(listnode *)malloc(sizeof(listnode));/*生成头结点*/ head->data=10; head->next=NULL;

p=(listnode *)malloc(sizeof(listnode));/*生成第一个要插入的新结点*/

p->data=20; p->next=NULL; q=head;

while(q->next!=NULL) {

q=q->next; }

q->next=p; p=(listnode *)malloc(sizeof(listnode)); p->data=30; p->next=NULL; q=head;

while(q->next!=NULL) {

q=q->next; }

q->next=p; p=(listnode *)malloc(sizeof(listnode));/* p->data=40; p->next=NULL; q=head;

while(q->next!=NULL) {

q=q->next; }

q->next=p; q=head; do {

cout<data; cout<<\ q=q->next; }

while(q->next!=NULL); cout<data; cout<<\ q=q->next; }

运行结果如图

实验3 查找算法 实验题目：二分查找算法

实验目的：掌握二分查找算法的基本原理，使用vc++6.0语言编写程序。 实验内容：

（1） 查找的概念

查找又称检索，简单讲就是查找表。一个查找过程，就是对于给定的元素K，找出表中关键字值等于的记录。查找成功，确定其关键字值等于K的记录存在；查找失败，确定关键字为K的记录不在表中。

（2）二分查找算法的基本原理

如果顺序查找表的元素按照关键字的值有序存放，那么可利用高效的二分查找来完成查询。条件假定元素按关键字的值升序排列，将给定的数据与有序表中间位置的元素做比较，若两者相等则查找成功；若前者小于后者则在中间位置左边的元素中继续查找；若前者大于后者则在中间位置右边的元素中继续查找。不断重复这一过程直到查找成功，或者直到查找区间缩小为一个元素时却仍未找到目标，则查找失败。

（3）给出一组有序数列，对其中某个数进行二分查找，建立一个.cpp程序。 实验步骤：

① 设置查找区间初值，设下界low = 0，设上界high = length-1。 ② 若low≤high则计算中间位置mid = (low +high)/2。 ③ 若keydata[mid]，则设low = mid+1并继续执行步骤②；

若key=data[mid]则查找成功，返回目标元素位置mid+1（位置从1计数）。 ④ 若当low=high时，key!=data[mid]则查找失败，返回0。 实验结果

二分法查找数据源程序：

#include\#include #include int a[10];

int BinSearch(int key,int length) {

int low, high, mid; low = 0;

high =length-1; while (low <= high) {

mid = (low + high) / 2; if(key==a[mid]) {

return mid; } //查找成功 else {

if(key

high = mid-1;

} //继续在前半区间进行查找 else {

low = mid + 1; }

} //继续在后半区间进行查找 }

return 0; //不存在待查元素 }

void main(void) {

int i,k=0,r;

cout<<\请输入一个要查找的数字:\ cin>>k;

for(i=0;i<10;i++) {

a[i]=i; }

r=BinSearch(k,10); if(r!=0) {