计算机软件技术基础上机实践报告1

计算机软件技术基础上机实践报告

姓名 黄明 学号 1043031197 信息 10级电力专业

电话 13668136448

实验一、线性表的插入和查找

一、算法描述

1、建立含有若干个元素的升序单链表，对其进行插入和查找等操作。构造函数node *insert (node *head, int num)，实现把一个结点插入链表，仍保持链表上各结点的升序关系，并在主函数中添加函数的测试；构造函数node *find(node *head,int k-1)，实现查找第K-1个结点，且由P指向该结点，并在主函数中测试。

2、线性表插入：在升序链表head中插入data值为num结点s。首先要判断head链表是否为空，若为空则直接返回s并将s->next赋值为NULL；其次再判断head头结点data域的值与要插入的num值得大小关系，若data域值比插入num的值大则将s指向head并返回s；反之则在head链表中找到相应位置插入并返回head，此时完成两个指针的修改：新结点s的指针域指向原结点pr的后继结点p：s->next

= p ；原结点pr的指针域指向新结点s：pr->next = s。

3、线性表查找：实现查找第K-1个结点，且由P指向该结点并返回。首要判断要实现查找的结点k-1是否超过head链表的边长，若超过表长则返回NULL；其次进入循环完成查找并返回p。这两步可以用先while(p != NULL && j

二、程序编码

1、程序代码如下： #include struct node{ int data; node *next; };

// 将num插入到head开头的升序链表的合适位置，使新链表仍然为升序的

node *insert(node *head ,int num) {

node *s,*pr,*p; s=new node; s->data=num; if(head==NULL)

{

s->next = NULL; return s; }

pr=head; p=head->next; if (pr->data>num) {

s->next=pr; return s; }

while(p!=NULL&&p->datanext; }

s->next=p; pr->next=s; return head; }

//查找第K-1个结点，并由P指向该结点

node *find(node *head,int k-1) {

node *p; p=head; int j=o;

while(p != NULL && j

p = p->next ; j++; }

if(j != i-1 ) return(NULL); else return p; }

node*create_sort(void) {

node*p1,*head=0; int a;

cout<<\建立一条有序链表，请输入数据，以 cin>>a; while(a!=-1)

-1结束：\ {

p1=new node; p1->data=a;

head=insert(head,a); cin>>a; }

return(head); }

//输出链表上各个结点的值 void print(const node *head) {

const node *p; p=head;

cout<<\链表上各个结点的数据为:\\n\ while(p!=NULL) {

cout<data<<'\\t'; p=p->next; }

cout<<'\\n'; }

//删除链表上具有指定值的一个结点