VC++线性表链表的教程.doc

网络协议仿真教学系统实验教材（基本版） PAGE 6 实验二　线性表存储结构的实现 【实验目的】 1．通过实验理解线性表的存储结构。 2. 通过实验掌握顺序表和链表的操作。 【实验学时】 2学时 【实验类型】 验证型 【实验内容】 1．掌握线性表的数据结构的特点。 2．掌握顺序表的编码实现及顺序表上的各种操作。 3．掌握链表的编码实现及其各种操作。 【实验原理】 1．线性表数据结构实现 现有一线性表（12，3，5，34，65，10，7，34，79），采用顺序存储结构，上机完成以下任务： (1)利用数组建立该线性表的顺序存储结构。 (2)在34和65之间插入数据50。 (3)删除元素65。 (4)查找值为100的元素，若该元素不存在，将其插入到表的最后。 2．链表数据结构实现 将线性表采用链式存储结构，完成上述的各项任务。 （1） 在对话框头文件或者CPP文件头部，增加如下内容： #define NULL 0 typedef int node_type; typedef struct linkednode{ node_type data; struct linkednode *next; } snode, *ptr; #define newptr() (ptr)malloc(sizeof(snode)) 则申请新节点可以使用： p=newptr(); 在C++中，也可以使用 p= new snode; 删除节点则使用： delete p; （2) 在链表表头插入节点： 设指针p指向一个新节点，要插入链表中。 p-next = head; head = p; （在链表中间插入节点： 设要把指针p对应节点插入到q节点后面， p-next = q-next; q-next = p; （4) 删除表头节点 p = head; head = head-next; free(p); （在链表中间删除节点： 设要删除q节点后面的一个节点， p = q-next; q-next = p-next; free(p); 3．构造链表数据结构的步骤 （1） 构造一个空链表 （2）反复执行下列步骤 读入一个元素值 申请一个存储节点 构造一个节点（即给这个节点的值域赋值为读入的元素值） 将该节点插入链表中 直到读入的元素是结束标记。 其中第4步插入节点可以有三种不同的插入方法：向前插入、向后插入、有序插入。 【实验步骤】 练习一：线性表实现 1 建立一个新的工程，在界面上添加按钮如下： 显示数据DISP 初始化数据INIT 插入数据INSERT 删除数据DELETE 尾部添加数据ADDTAIL 清除数据CLEAR 这6个按钮，分别对应了实验内容中的各项功能。为它们修改ID，标题，并添加事件处理函数。 2 在类视图，为对话框类增加成员变量数组：int data[30]; 增加成员变量int datalen （立：在classview中选中类--Dlg右击第四项添加成员变量） 3 在类的初始化函数OnInitDialog（）中，把datalen赋值为0； 4 在初始化数据按钮函数中，初始化数组data[]和数据长度datalen； data[0]=12; data[1]=3; data[2]=5; data[3]=34; data[4]=65; data[5]=10; data[6]=7; data[7]=34; data[8]=79; datalen = 9; 5 编制显示数据函数： { char str[300]; sprintf(str,数组共有%d个数据\r\n, datalen); m1 += str; for(int i=0; idatalen; i++) { sprintf(str,第%d个数据：%d\r\n, i+1, data[i]); m1 += str; } UpdateData(false); } 6 编制插入数据函数： { int pos; pos = Find2Data(34,65); if( pos=0 ) InsertData(pos, 50); else m1 += 没有找到数据（34,65）\r\n; } 其中使用到两个函数： int CDsexDlg::Find2Data(int d1, int d2) { int i; int posf; posf = -1; for ( i=0; idatalen-1; i++) { if( data[i]== d1 (data[i+1]==d2) ) posf=i; } return posf; } void CDsexDlg::InsertDa