求数据结构试验 线性表的顺序存储结构
#include
#include
#include
#define OVERFLOW 0
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100//线性表存储空间的初始增量
#define LISTINCREMENT 10 // ?
typedef struct{
int * elem;// 存储空间基址
int length;//当前长度
int listsize;//当前分配的存储容量
}SqList;
SqList L;
int InitList_Sq(SqList & L){
//构造一个新的线性表。
L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
if(!L.elem)exit(OVERFLOW);//存储容量失败
L.length=0; //空表长度为0
L.listsize=LIST_INIT_SIZE;//存储初始容量
return OK;
}//InitList_Sq
int LIstInsert_Sq(SqList & L,int i,int e){
//在顺序线性表L中第i位置之前插入新的元素e
if(iL.length+1) return ERROR;
if(L.length>=L.listsize){
int * newbase=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
if(!newbase)exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
int * q=&(L.elem[i-1]);
for(int * p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;
*q=e;
++L.length;
return OK;
}
int ListDelete_Sq(SqList&L,int i,int &e)
{
if((iL.length))return ERROR;
int *p=&(L.elem[i-1]);
e=*p;
int *q=L.elem+L.length-1;
for(++p;p<=q;++p)*(p-1)=*p;
--L.length;
return OK;
}
void main()
{
SqList L;
int i,n;
int e;
cout<<"输入顺序表的个数："<<endl;
cin>>n;
int *p=(int *)malloc(n*sizeof(int));
InitList_Sq(L);
cout<<"输入线性表"<<n<<"个元素的值"<<endl;
for(i=0;i<n;i++)
{
cin>>p[i];
L.elem[i]=p[i];
}
cout<<endl;
L.length=i;
cout<<endl;
cout<<"输入要插入元素的值"<<endl;
cin>>e;
cout<<endl;
cout<<"输入要插入的位置"<<endl;
cin>>i;
LIstInsert_Sq( L, i, e);
for(i=0;i<n+1;i++)
cout<<L.elem[i];
cout<<endl;
cout<<"输入要删除的位置"<<endl;
cin>>i;
ListDelete_Sq(L,i,e)
;for(i=0;i<n;i++)
cout<<L.elem[i];
free(p);
C++代码编写的
#include#includeusing namespace std;typedef int ElemType;typedef struct LNode{ ElemType data; struct LNode *next;} LinkList;void CreatListR(LinkList *&L,ElemType a[],int n){ LinkList *s,*r; int i; //L=(LinkList *)malloc(sizeof(LinkList)); L=new LinkList(); r=L; for(i=0;idata=a[i]; r->next=s; r=s; } r->next=NULL;}void DispList(LinkList *L){ LinkList *p=L->next; while(p!=NULL) { coutdatanext; } coutnext; } if(p==NULL) return 0; else { s=new LinkList(); s->data=e; s->next=p->next; p->next=s; return 1; }}int ListDelete(LinkList *&L,int i){ int j=0; LinkList *p=L,*q; while(jnext; } if(p==NULL) { return 0; } else { q=p->next; if(q==NULL) { return 0; } p->next=q->next; int a=q->data; free(q); return a; }}int main(){ LinkList *L,*L1; int a[]={1,5,7,9,12,18,19,20,30,43,45,56,41,42,78}; int n=15,i,x,y,j; CreatListR(L,a,n); DispList(L); cout>i; cout>x; ListInsert(L,i,x); DispList(L); cout>j; y=ListDelete(L,j); DispList(L); cout<<y<<endl; return 0;}
顺序表的顺序查找算法：
int Seqsearch1(int r[],int n,int k)
{
r[0]=k;
i=n;
while(r[i]!=k)
i--;
return i;
}
单链表的顺序查找算法：
int Seqsearch2(Node<int> *first,int k)
{
p=first->next;j=1;
while(p!=NULL&&p->data!=k)
{
p=p->next;
j++;
}
if(p->data==k)return j;
else return 0;
}
折半查找：
非递归
int Binsearch1(int r[],int n,int k)
{
high=n;low=1;
while(low<=high)
{
mid=(high+low)/2;
if(k<mid) high=mid-1;
else if(k>mid) low=mid+1;
else return mid;
}
return 0;
}
递归
int Binsearch2(int r[],int low,int high,int k)
{
if(low>high) return 0;
else
{
mid=(low+high)/2;
if(K<mid) return Binsearch2(r,low,mid-1,k);
else if(K>mid) return Binsearch2(r,mid+1,high,k);
else return mid;
}
}
二叉树排序：
class BiSortTree
{
public:
BiSortTree(int a[],int n);
~BiSortTree();
void InsertBST(BiNode<int> *root,BiNode<int> *s);
void DeleteBST(BiNode<int> *p,BiNode<int> *f);
BiNode<int>* SearchBST(BiNode<int> *root,int k);
private:
BiNode<int> *root;
};
void BiSortTree::InsertBST(BiNode<int> *root,BiNode<int> *s);
{
if(root==NULL) root=s;
else if(s->data<root->data) InsertBST(root->lchild,s);
else InsertBST(root->rchild,s);
}
BiSortTree::BiSortTree(int r[],int n)
{
for(i=0;i<n;i++)
{
s=new BiNode<int>;s->data=r[i];
s->lchild=s->rchild=NULL;
InsertBST(root,s);
}
}
void BiSortTree::DeleteBST(BiNode<int> *p,BiNode<int> *f)
{
if(!p->lchild&&!p->rchild)
{
f->lchild=NULL;
delete p;
}
else if(!p->lchild)
{
f->lchild=p->rchild;
delete p;
}
else if(!p->rchild)
{
f->lchild=p->lchild;
delete p;
}
else
{
par=p;s=p->rchild;
while(s->lchild!=NULL)
{
par=s;
s=s->lchild;
}
p->data=s->data;
if(par==p) par->rchild=s->rchild;
else par->lchild=s->rchild;
delete s;
}
}
BiNode<int> *BiSortTree::SearchBST(BiNode<int> *root,int k)
{
if(root==NULL) return NULL;
else if(root->data==k) return root;
else if(root->data<k) return SearchBST(root->lchild,k);
else return SearchBST(root->rchild,k);
}
闭散列表的查找算法：
int HashSearch1(int ht[],int m,int k)
{
j=H[k];
if(ht[j]==k) return j;
i=(j+1)%m;
while(ht[i]!=Empty&&i!=j)
{
if(ht[i]==k) return i;
i=(i+1)%m;
}
if(i==j) throw"溢出";
else ht[i]=k;
}
开散列表的查找算法：
Node<int> *HashSearch2(Node<int> *ht[],int m,int k)
{
j=H[k];
p=ht[j];
while(p&&p->data!=k)
p=p->next;
if(p->data==k) return p;
else
{
q=new Node<int>;q->data=k;
q->next=ht[j];
ht[j]=q;
}
}
排序：
插入
直接插入排序算法：
void InsertSort(int r[],int n)
{
for(i=2;i<=n;i++)
{
r[0]=r[i];
for(j=i-1;r[0]<r[j];j--)
r[j+1]=r[j];
r[j+1]=r[0];
}
}
希尔排序算法：
void ShellSort(int r[],int n)
{
for(d=n/2;d>=1;d=d/2)
{
for(i=d+1;i<=n;i++)
{
r[0]=r[i];
for(j=i-d;j>0&&r[0]<r[j];j=j-d)
r[j+d]=r[j];
r[j+d]=r[0];
}
}
}
交换
起泡排序：
void BubbleSort(int r[],int n)
{
exchange=n;
while(exchange)
{
bound=exchange;exchange=0;
for(j=1;j<bound;j++)
if(r[j]>r[j+1])
{
r[j]<-->r[j+1];
exchange=j;
}
}
}
快速排序：
int Partition(int r[],int first,int end);
{
i=first;j=end;
while(i<j)
{
while(i<j&&r[i]<=r[j]) j--;
if(i<j)
{
r[i]<-->r[j];
i++;
}
while(i<j&&r[i]<=r[j]) i++;
if(i<j)
{
r[i]<-->r[j];
j--;
}
}
return i;
}
void QuickSort(int r[],int first,int end)
{
if(first<end)
{
pivot=partition(r,first,end)
QuickSort(r,first,pivot-1);
QuickSort(r,pivot+1,end);
}
}
选择
简单选择排序：
void SelectSort(int r[],int n)
{
for(i=1;i<n;i++)
{
index=i;
for(j=i+1;j<n;j++)
if(r[j]<r[index]) index=j;
if(index!=i) r[i]<-->r[index];
}
}
堆排序：
void Sift(int r[],int k,int m)
{
i=k;j=2*i;
while(j<=m)
{
if(j<m&&r[j]<r[j+1])j++;
if(r[i]>r[j]) break;
else
{
r[i]<-->r[j];
i=j;j=2*i;
}
}
}
void HeapSort(int r[],int n)
{
for(i=n/2;i>=1;i--)
sift(r,i,n);
for(i=1;i<n;i++)
{
r[1]<-->r[n-i+1];
sift(r,1,n-i);
}
}
归并
二路归并排序：
void Merge(int r[],int r1[],int s,int m,int t)
{
i=s;j=m+1;k=s;
while(i<=m&&j<=t)
{
if(r[i]<=r[j]) r1[k++]=r[i++];
else r1[k++]=r[j++];
}
if(i<=m) while(i<=m)
r1[k++]=r[i++];
else while(j<=t)
r1[k++]=r[j++];
}
void Merge(int r[],int r1[],int n,int h)
{
i=1;
while(i<=n-2h+1)
{
Merge(r,r1,i,i+h-1,i+2h-1);
i=i+2*h;
}
if(i<n-h+1) Merge(r,r1,i,i+h-1,n)
else for(k=i;k<=n;k++)
r1[k]=r[k];
}
void MergeSort1(int r[],int r1[],int n)
{
h=1;
while(h<n)
{
MergePass(r,r1,n,h);
h=2*h;
MergePass(r1,r,n,h);
h=2*h;
}
}
void MergeSort2(int r[],int r1[],int s,int t)
{
if(s==t) r1[s]=r[t];
else
{
m=(s+t)/2;
MergeSort2(r,r1,s,m);
MergeSrot2(r,r1,m+1,t);
Merge(r1,r,s,m,t);
}
}
#include<iostream.h>
#include<stdlib.h>
#include <malloc.h>
#define OVERFLOW 0
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100//线性表存储空间的初始增量
#define LISTINCREMENT 10 // ?
typedef struct{
int * elem;// 存储空间基址
int length;//当前长度
int listsize;//当前分配的存储容量
}SqList;
SqList L;
int InitList_Sq(SqList & L){
//构造一个新的线性表。
L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
if(!L.elem)exit(OVERFLOW);//存储容量失败
L.length=0; //空表长度为0
L.listsize=LIST_INIT_SIZE;//存储初始容量
return OK;
}//InitList_Sq
int LIstInsert_Sq(SqList & L,int i,int e){
//在顺序线性表L中第i位置之前插入新的元素e
if(i<1||i>L.length+1) return ERROR;
if(L.length>=L.listsize){
int * newbase=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
if(!newbase)exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
int * q=&(L.elem[i-1]);
for(int * p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;
*q=e;
++L.length;
return OK;
}
int ListDelete_Sq(SqList&L,int i,int &e)
{
if((i<1)||(i>L.length))return ERROR;
int *p=&(L.elem[i-1]);
e=*p;
int *q=L.elem+L.length-1;
for(++p;p<=q;++p)*(p-1)=*p;
--L.length;
return OK;
}
void main()
{
SqList L;
int i,n;
int e;
cout<<"输入顺序表的个数："<<endl;
cin>>n;
int *p=(int *)malloc(n*sizeof(int));
InitList_Sq(L);
cout<<"输入线性表"<<n<<"个元素的值"<<endl;
for(i=0;i<n;i++)
{
cin>>p[i];
L.elem[i]=p[i];
}
cout<<endl;
L.length=i;
cout<<endl;
cout<<"输入要插入元素的值"<<endl;
cin>>e;
cout<<endl;
cout<<"输入要插入的位置"<<endl;
cin>>i;
LIstInsert_Sq( L, i, e);
for(i=0;i<n+1;i++)
cout<<L.elem[i];
cout<<endl;
cout<<"输入要删除的位置"<<endl;
cin>>i;
ListDelete_Sq(L,i,e)
;for(i=0;i<n;i++)
cout<<L.elem[i];
free(p);
#include<stdlib.h>
#define max_sq_size 100
void creat(int *sqlist) {
int a, b, i;
printf("请输入节点数\n：");
scanf("%d", &a);
if(a<0 ||a > max_sq_size){
printf("节点数不正确！\n");
system("PAUSE");
}
for(i=0; i != a; i++) {
printf("请输入第%d 个节点\n",i+1);
scanf("%d", &b);
sqlist[i] = b;
}
}
void hebing(int *sqlist1, int *sqlist2) {
int i, j, a;
i = 0;
while(sqlist1[i]) {
printf("########\n");
a = sqlist1[i];
j = 0;
while(a != sqlist2[j]&&sqlist2[j]) {
printf("*****\n");
j++;
}
if( a != sqlist2[j]) sqlist2[j] = a;
i++;
}
}
void display(int *sqlist) {
int i= 0;
while(sqlist[i]) {
printf("%5d", sqlist[i]);
i++;
}
printf("\n");
}
int main(void )
{
int sqlist1[max_sq_size] =;
int sqlist2[max_sq_size]= ;
creat(sqlist1);
creat(sqlist2);
display(sqlist1);
display(sqlist2);
hebing(sqlist1, sqlist2);
display(sqlist2);
system("PAUSE");
}//草，本来以为很简单的，结果差错查了一个小时。汗
都有参考了，为什么不自己做做呢？
自己没有一点想法么
撒昨血康： #include <stdio.h>#define OK 1 #define ERROR -1 #define TURE 1 #define FALSE 0 #define MAXLENGTH 20struct sequencelist {int data[MAXLENGTH];int length; };//get list elements //make sure elemet is NOT NULL when calling. int ...
河间市18581057285： 数据结构题目1.线性表有两种存储结构:一是顺序表,二是链表.试问:(1)如果有 n 个线性表同时并存,并且在处理过程中各表的长度会动态变化,线性... - ？
撒昨血康：[答案] 1(1):链表,理由是链表能够高效的执行插入删除操作,适用于元素变化较多的情形1(2):顺序表,不方便插入删除,但能高效的读取线性表中的元素2: 链表可以克服弱点一,只需要改相邻指针,不需要移动元素;可以克服弱点二,控件动态分配...
河间市18581057285： 数据结构 算法设计题 有一个学生成绩线性表,用顺序存储方式进行存储,请编写一个时间复杂度较小的算法, - ？
撒昨血康： 如果是从头到尾,见到一个满足于60分~70分之间的学生成绩,就删除,显然时间复杂度大. 可以这样去做: 1、用一个指示器i,从前往后找出第一个满足于60分~70分之间的学生成绩; 2、再用另一个指示器j,从尾部开始,由后向前找出第一个不满足于60分~70分之间的学生成绩;3、将i,j所指元素交换一下,直到两指示器相撞,删除结束,删除的操作,利用表长来实现!也就是所有60分~70分之间的学生成绩都在表的后部.
河间市18581057285： 求高手用C写一段线性表的顺序存储(包括创建,插入,删除和查找),不用很复杂,最简单的就可以了! - ？
撒昨血康： #include<malloc.h> /* malloc()等 */ #include<stdio.h> /* EOF(=^Z或F6),NULL */ #include<stdlib.h> /* atoi() */ #include<io.h> /* eof() */ /* 函数结果状态代码 */ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define ...
河间市18581057285： 线性表的顺序存储结构的题目,我自己的答案是n/2,书上的答案是(n - 1)/2,各位帮我看看呗 - ？
撒昨血康： 举个例子,3个数据的线性表,假设插入数据是m,那么可能的插入是1,m2.m3.m4.m>a3,移动0个 共移动:0+1+2+3=6 插入次数:4 平均移动步数:6/4=1.5 应该是书上答案错误.
河间市18581057285： 1、 建立线性表的(动态分配)顺序存储结构. - ？
撒昨血康： 以下步骤:一、线性表的顺序表示 用一组地址连续的存储单元依次存储线性表的数据元素.C语言中的数组即采用顺序存储方式.2000:0001 2000:0003 2000:0005 2000:0007 2000:0009 2000:0011 2000:0013 2000:0015 2000:0017 ... 2000:...
河间市18581057285： 跪求C数据结构高手帮忙~~线性表的顺序存储及其操作 - ？
撒昨血康： #include#include#define LIST_INIT_SIZE 100#define LISTINCREMENT 10 typedef struct{ int * elem; int length; int listsize; }SqList;//SqList sq; void InitList_Sq(SqList *sq) //初始化列表 { sq->elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int)); sq->length=...
河间市18581057285： 什么是线性表的顺序存储结构?用自然语言描述采用队列存储数据时候删除数据的过程? - ？
撒昨血康： 在计算机内部用一组地址连续的储存单元来依次储存线性表中的元素,这种储存结构就叫顺序储存结构.自然语言描述采用队列存储数据时候删除数据的过程:删除队头元素,后一位前移.
河间市18581057285： 已知线性表L=(10, 15, 30, 42, 51, 62), 请分别画出该线性表的顺序存储结构和链式存储结构. - ？
撒昨血康： 不是很懂你的意思,线性表顺序存储是连续的,把数据写在连续的空间就是,而链式存储不连续,把数据分多个空间就是
河间市18581057285： 用C语言数据结构【线性表的顺序存储结构】知识解决如下问题,请高手指点! - ？
撒昨血康： 无论是用链表实现还是用数组实现都有一个共同点:要模拟整个 游戏过程,不仅程序写起来比较烦,而且时间复杂度高达O(nm),当n ,m非常大(例如上百万,上千万)的时候,几乎是没有办法在短时间 内出结果的.我们注意到原问题仅仅是要...
