『壹』 請問一下數據結構中對稱矩陣的壓縮存儲的一 一對應關系怎麼算的呀。
先看上面一個：
下三角有i>=j
第1行一個，第2行兩個，。。。，第i-1行i-1個（i, j下標都是從1開始的）
所以第i行前有1+2+...+(i-1)= i(i-1)/2個元素
再看本行，本元素前有j-1個元素
因為計算的是元素之間的位置差，因此就是i(i-1)/2+(j-1)了
下面一個上三角i<j：
對於對稱矩陣有a(i,j)=a(j,i)，即行列互換，代入上式即可得
『貳』 關於數據結構——線性表一問題
#include<iostream.h>
#include"SqList.h"
void fun2(SqList I)
{
int temp,p,q;
q=I.length/2;
p=I.length/2;
for(int i=1;i<=p;i++)
{
temp=I.elem[q+i];
I.elem[q+i]=I.elem[q-i];
I.elem[q-i]=temp;
}
cout<<"輸出順序表:"<<endl;
for(int w=0;w<I.length;w++) cout<<I.elem[w]<<" ";
}
void fun1(SqList M)
{
int temp,q,s;
q=M.length/2;
for(int i=0;i!=q;i++)
{
s=M.length-i-1;
temp=M.elem[i];
M.elem[i]=M.elem[s];
M.elem[s]=temp;
}
cout<<"輸出順序表:"<<endl;
for(int v=0;v<M.length;v++) cout<<M.elem[v]<<" ";
}
int main()
{
SqList L;
InitList_Sq(L);
Create_Sq(L);
Print_Sq(L);
switch(L.length%2)
{
case 0:fun1(L);break;
case 1:fun2(L);break;
}
return 0;
}
SqList
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
#define LIST_INIT_SIZE 10
#define LISTINCREMENT 2
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
Status InitList_Sq(SqList &L)
{
// 構造一個空的線性表L。
L.elem = new ElemType[LIST_INIT_SIZE];
if (!L.elem) return OVERFLOW; // 存儲分配失敗
L.length = 0; // 長度為0
L.listsize = LIST_INIT_SIZE; // 初始存儲容量
return OK;
} // InitList_Sq
Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
ElemType *p,*q;
if (i < 1 || i > L.length+1) return ERROR;
q = &(L.elem[i-1]); // q指示插入位置
for (p = &(L.elem[L.length-1]); p >= q; --p)
*(p+1) = *p;
// 插入位置及之後的元素右移
*q = e; // 插入e
++L.length; // 表長增1
return OK;
} // ListInsert_Sq
Status ListDelete_Sq(SqList &L, int i, ElemType &e)
{
ElemType *p,*q;
if ((i < 1) || (i > L.length)) return ERROR;
p = &(L.elem[i-1]); // p為被刪除元素的位置
e = *p; // 被刪除元素的值賦給e
q = L.elem+L.length-1; // 表尾元素的位置
for (++p; p <= q; ++p) *(p-1) = *p; // 被刪除元素之後的元素左移
--L.length; // 表長減1
return OK;
} // ListDelete_Sq
void Create_Sq(SqList &L)
{
cout<<"請輸入元素個數:";
cin>>L.length;
cout<<"創建順序表"<<endl;
for(int i=0;i<L.length;i++)
{
cout<<"請輸入第"<<i+1<<"個數：";
cin>>L.elem[i];
}
}
void Print_Sq(SqList &L)
{
cout<<"輸出順序表:"<<endl;
for(int i=0;i<L.length;i++) cout<<L.elem[i]<<" ";
}
『叄』 線性表中所有的元素所佔的存儲空間是連續的，是什麼意思
線性表中有鏈表和順序表兩類，順序表所佔的存儲空間必須連續，鏈表沒有這個要求，連續指的是存儲空間的連續，順序存儲結構中，線性表中每一個數據元素在計算機存儲空間中的存儲地址由該元素在線性表中的位置序號唯一確定。
線性表是最常用的數據結構，它由一組數據元素組成。
注意：這里的數據元素是一個廣義的數據元素，並不僅僅是指一個數據。如，矩陣、學生記錄表等。
非空線性表的結構特徵：
有且只有一個根結點，它無前件
有且只有一個終端結點，它無後件
除根結點和終端結點之外，所有的結點有且只有一個前件和一個後件。線性表中結點的個數稱為結點的長度n。當n=0時，稱為空表。
『肆』 查找線性表的第K個元素(順序表，鏈表) 網上有找到答案，但是沒說明，求發一個帶說明的答案，謝謝！
int GetElem();
int InstInsert();
typedef int ElemType;
typedef struct{
ElemType *elem; //存儲空間基地址
int length; //當前長度
int listsize;//當前分配的存儲容量
}SqList;
int InitList(SqList *L){
L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L->elem)exit(-1);//存儲空間分配失敗
L->length=0; //空表長度為0
L->listsize=LIST_INIT_SIZE; //初始存儲容量
printf("線性鏈表創建成功\n");
return OK;
}
int Input(SqList *L){
ElemType temp,*newbase;
printf("輸入順序列表的數據，以0為結束標志\n");
scanf("%d",&temp);
while(temp!=0){
if(L->length>=L->listsize){
newbase=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!newbase) exit(-1);//存儲空間分配失敗
L->elem=newbase; //空間新基地址
L->listsize+=LISTINCREMENT; //增加存儲容量
}
L->elem[L->length++]=temp;
scanf("%d",&temp);
}
printf("輸入數據結束！！\n");
return OK;
}
int Onput(SqList *L){
int i=0;
printf("輸出線性表數據：");
while(i<L->length){
printf("%d\t",L->elem[i]);
i++;
}
printf("\n");
}
int ClearList(SqList *L){
L->length=0;
printf("清除成功!\n");
return OK;
}
void ListEmpty(SqList L){
if(L.elem!=NULL)
printf("true!\n");
else
printf("false!\n");
}
void ListLength(SqList L){
printf("線性表的長度是：%d\n",L.length);
return ;
}
int GetElem(SqList L,int i,SqList *e){
e=L.elem[i-1];
return e;
}
void PriorElem(SqList L,int cur_e,SqList *pre_e){
if(cur_e!=L.elem[0]){
pre_e=L.elem[0];
printf("前驅值為：%d\n",pre_e);
}
else
printf("pre_e無意義\n");
}
void NextElem(SqList L,int cur_e,SqList *next_e){
if(cur_e!=L.elem[L.length-1]){
next_e=L.elem[L.length-1];
printf("後繼值為：%d\n",next_e);
}
else
printf("next_e無意義\n");
}
int ListInsert(SqList *L,int i,int e){
ElemType *newbase,*p,*q;
if(1>i||i>(L->length+1))
return -1;
if(L->length>=L->listsize){ //新增內存
newbase=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); //開辟新內存空間
if(!newbase)
exit(-1); //存儲分配失敗
L->elem=newbase; //新基地址
L->listsize+=LISTINCREMENT; //新增內存容量
}
q=&(L->elem[i-1]);
for(p=&(L->elem[L->length-1]);p>=q;p--){
*(p+1)=*p;
}
*q=e;
++L->length;
return OK;
}
int ListDelete(SqList *L,int i,int e){
ElemType *p,*q;
if(i<1||i>L->length)
return -1;
q=&(L->elem[i-1]);
e=L->elem[i-1];
p=L->elem+L->length-1;
for(;p>=q;q++)
*q=*(q+1);
--L->length;
printf("刪除的值為：%d\n",e);
return OK;
}
『伍』 關於數據結構中的線性表的問題
線性表是邏輯定義，順序存儲或者鏈式存儲是其在內存中的存放形式
順序存儲是以元素存儲的空間位置表示元素邏輯關系，數組則是順序存儲中最為簡單的形式
鏈式存儲的線性表簡稱為鏈表，不過現在只要是鏈式存儲的不管邏輯結構是什麼樣的都叫鏈表
『陸』 求數據結構試驗 線性表的順序存儲結構
#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);