| « | June 2026 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | | | | | |
|
公告 |
| 暂无公告... |
| Blog信息 |
|
blog名称:
日志总数:32
评论数量:44
留言数量:0
访问次数:181942
建立时间:2005年1月4日 |
| |
|
 数据结构--线性表
文章收藏
eaglebetter 发表于 2006/8/6 0:17:07 |
| 数据结构--线性表2-1 线性表的定义与运算2-1-1 线性表的定义1．线性表的定义2．线性表举例（1） 简单的线性表（2） 复杂的线性表表2-1 学生入学情况登记简表学 号 姓 名 性 别 入学总分 01 丁一 男 440 02 马二 男 435 03 张三 女 438 04 李四 男 430 05 王五 女 445 06 赵六 男 428 07 钱七 女 432 08 孙八 男 437 09 冯九 女 426 10 郑十 女 425 3．线性表的二元组表示2-1-2 线性表的基本操作（1） 创建线性表：CreateList()（2） 求线性表的长度：LengthList(L)（3） 按值查找：SearchList(L,x)，x是给定的一个数据元素（4） 插入操作：InsList(L,i,x)（5） 删除操作：DelList(L，i)（6） 显示操作：ShowList(L)2-2 线性表的顺序存储2-2-1 顺序表datatype data[MAXLEN]; int last;typedef struct { datatype data[MAXLEN] int last;} SeqList; 2-2-2 顺序表上基本运算的实现1．顺序表的初始化SeqList *InitList() { SeqList *L;L=new SeqList; L->last=-1; // 初始的顺序表为空return L; }2．插入运算int InsList(SeqList *L，int i，datatype x){ int j; if (L->last==MAXLEN-1){ printf("顺序表已满！"); return(-1); // 顺序表已满，不能插入} if (i<1 || i>L->last+2) // 检查给定的插入位置的正确性 { printf("位置出错！");return(0); } for(j=L->last;j>=i-1;j--) // 结点移动 L->data[j+1]=L->data[j]; L->data[i-1]=x; // 新元素插入 L->last++; // last仍指向最后的元素 return (1); // 插入成功，返回} 3．删除运算 int DelList(SeqList *L;int i) { int j; if(i<1 || i>L->last+1) //检查空表及删除位置的合法性 { printf ("不存在第i个元素"); return (0); } for(j=i;j<=L->last;j++) //向上移动 L->data[j-1]=L->data[j]; L->last--; //last仍指向最后元素return(1); //删除成功}4．按值查找int LocationSeqList(SeqList *L, datatype x){ int i=0; while(i<=L.last && L->data[i]!= x) i++; if (i>L->last) return -1; else return i; // 返回的是存储位置}2-3 线性表的链式存储2-3-1 线性链表1．线性链式存储结构的特点（1）用一组任意的存储单元存储线性表的数据元素（2）单链表的每个结点由一个数据域和一个指针域组成（3）单链表的存取必须从头指针开始2．关于头指针、头结点和开始结点3．在C（或C++）中可以用“结构体指针”来描述typedef struct linknode { datatype data; struct linknode *next; } Node，*LinkList；LinkList H；p=new Node；2-3-2 线性链表上基本运算的实现1．建立线性链表（1） 在链表的头部插入结点建立线性链表void CreateList() // 建立线性表{node *head,*p,*s;char x;int z=1,n=0; // n用来存储表长head = NULL;p=head;printf("\n\t\t建立一个线性表");printf("\n\t\t说明：请逐个输入字符，结束标记为“x”！\n");while(z){ printf("\t\t输入：");scanf("%c",&x);getchar();if(x!='x') // 输入“x”完成建立{ s=new node;n++;s->data=x;s->next=head;head=s;}else z=0; // 输入循环结束}}（2） 在线性链表的尾部插入结点建立线性链表void CreateList() // 建立线性表{node *head,*p,*s;char x;int z=1,n=0; // n用来存储表长head=NULL;p=head;printf("\n\t\t建立一个线性表");printf("\n\t\t说明：请逐个输入字符，结束标记为“x”！\n");while(z){printf("\t\t输入：");scanf("%c",&x);getchar();if(x!='x') // 输入“x”完成建立{s=new node;n++;s->data=x;if(!head) head=s;elsep=s;s->next=NULL;p=s;}else z=0; // 输入循环结束}}2．求表长（1） 设L是带头结点的线性链表（线性表的长度不包括头结点）int LenList1 (LinkList L){ Node * p=L; // p指向头结点 int n=0; while (p->next) { p=p->next; n++ } // p所指的是第 n 个结点 return n;}（2） 设L是不带头结点的线性链表int LenList2 (LinkList L){ Node * p=L; int n; if (p==NULL) return 0; // 空表的情况 n=1; // 在非空表的情况下，p所指的是第一个结点while (p->next ) { p=p->next; n++ } return n;}3．查找操作（1） 序号查找 SearchList1(L,i)Node * SearchList1 (LinkList L, int i)// 在带头结点的线性链表L中查找第i个元素结点，找到返回其指针，否则返回空{ Node * p=L; int j=0;while (p->next !=NULL && j<i ){ p=p->next; j++; } if (j==i) return p; else return NULL;}（2） 值查找即定位 SearchList2(L,x)Node * SearchList2 ( LinkList L, datatype x) //在带头结点的线性链表L中查找值为x的结点，找到后返回其指针，否则返回空{ Node * p=L->next; while ( p!=NULL && p->data != x) p=p->next; return p;}4．插入q=L;while (q->next!=p) q=q->next; //找*p的直接前趋s->next=q->next; q->next=s;void InsList(int i,char x) // 插入结点元素,head为头指针,指向头结点{ node *s,*p;int j;s=new node;n++;s->data=x;if(i==0){ s->next=head;head=s;}else { p=head;j=1;while(p!=NULL&&j<i){ j++;p=p->next;}if(p!=NULL){ s->next=p->next;p->next=s;}else printf("\t\t未找到！\n");}}5．删除 q->next=p->next;delete (p);s=p->next;p->next=s->next;delete(s);void DelList(char x) // 删除结点元素{node *p,*q;if(head==NULL) {printf("\t\t链表下溢！\n");return;}if(head->next==NULL) {printf("\t\t线性表已经为空！");return;}q=head;p=head->next;while(p!=NULL&&p->data!=x){q=p;p=p->next;}if(p!=NULL){q->next=p->next;delete p;n--;printf("\t\t %c已经被删除！",x);}elseprintf("\t\t未找到！\n");}2-3-3 循环链表1．特点2．循环链表上的操作P->NEXT==head;3．在循环链表中设尾指针可以简化某些操作p= T1 –>next; //保存T1 的头结点指针T1->next=T2->next->next; //头尾连接free(T2->next); //释放第二个表的头结点T2->next=p; //组成循环链表4．关于存储密度2-3-4 双向链表1．单向链表的缺点2．双向链表3．双链表的C（或C++）语言描述struct cdlist{datatype data; //结点数据struct cdlist *prior; //指向前趋结点的指针struct cdlist *next; //指向后继结点的指针}4．双链表的操作（1） 删除结点（2） 插入结点小结实验2 线性表子系统1．实验目的2．实验内容3．参考程序#include<stdio.h>// 线性表子系统实验typedef struct linknode{char data;struct linknode *next;}node;node *head;int n=0; // 线性表长度void CreateList() // 建立线性表{node *p,*s;char x;int z=1;head=new node;p=head;printf("\n\t\t建立一个线性表");printf("\n\t\t说明：请逐个输入字符，结束标记为‘x’！\n");while(z){printf("\t\t输入：");scanf("%c",&x);getchar();if(x!='x'){s=new node;n++;s->data=x;p->next=s;s->next=NULL;p=s;}else z=0;}}void InsList(int i,char x) // 插入结点元素{node *s,*p;int j;s=new node;n++;s->data=x;if(i==0){s->next=head;head=s;}else{p=head;j=1;while(p!=NULL&&j<i){j++;p=p->next;}if(p!=NULL){s->next=p->next;p->next=s;}else printf("\t\t未找到！\n");}}void DelList(char x) // 删除结点元素{node *p,*q;if(head==NULL) {printf("\t\t链表下溢！\n");return;}if(head->next==NULL) { printf("\t\t线性表已经为空！");return;}q=head;p=head->next;while(p!=NULL&&p->data!=x){ q=p;p=p->next;}if(p!=NULL){ q->next=p->next;delete p;n--;printf("\t\t %c已经被删除！",x);}elseprintf("\t\t未找到！\n");}void ShowList() // 显示线性表{ node *p=head;printf("\n\t\t显示线性表的所有元素：");if(head->next==NULL||p==NULL)printf("\n\t\t链表为空！\n");else{printf("\n\t\t");while(p->next!=NULL){ printf("%5c",p->next->data);p=p->next;}}}void SearchList(char x) // 查找线性表元素{ node *p;int i=1;if(head==NULL) { printf("\t\t链表下溢！\n");return;}if(head->next==NULL) { printf("\t\t线性表为空！没有任何内容！");return;}p=head->next;while(p!=NULL&&p->data!=x){ p=p->next;i++;}if(p!=NULL)printf("\t\t 在第%d位上找到值为%c的结点！",i,x);elseprintf("\t\t未找到值为%c的结点！\n",x);}void main(){ head=NULL;int choice,i,j=1;char x;while(j){ printf("\n\n\n\n");printf("\t\t\t 线 性 表 子 系 统\n");printf("\n\t\t**********************************");printf("\n\t\t* 1----------建 表 *");printf("\n\t\t* 2----------插 入 *");printf("\n\t\t* 3----------删 除 *");printf("\n\t\t* 4----------显 示 *");printf("\n\t\t* 5----------查 找 *");printf("\n\t\t* 6----------求 表 长 *");printf("\n\t\t* 0----------返 回 *");printf("\n\t\t**********************************\n");printf("\t\t请选择菜单号(0--6)：");scanf("%d",&choice);getchar();if(choice==1)CreateList();else if (choice==2){ printf("\n\t\t请输入的位置i和数值x(输入格式：i，x):");scanf("%d,%c",&i,&x);InsList(i,x);}else if (choice==3){ printf("\n\t\t请输入要删除的数值：");scanf("%c",&x);DelList(x);}else if (choice==4)if(head==NULL)printf("\n\t\t请先建立线性表！");else ShowList();else if (choice==5){ printf("\n\t\t请输入要查找的元素：");scanf("%c",&x);SearchList(x);}else if (choice==6){ printf("\n\t\t表长为%d",n);}else if (choice==0)j=0;else printf("\n\t\t输入错误！请重新输入！\n");}} |
|
|
回复:数据结构--线性表
文章收藏
怀枫(游客)发表评论于2006/11/5 22:23:45 |
| 能不能只给我创建个线性表，其他的算法不要，只要线性表。谢谢了
|
|
|
回复:数据结构--线性表
文章收藏
风(游客)发表评论于2006/10/29 16:23:53 |
|
» 1 »
|