기술나눔

데이터 구조(2부)--선형 테이블

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

목차

1. 기본 개념

2. 선형 테이블의 기본 동작

3. 서열표

(1).정적 할당

(2).동적 할당

(3) 시퀀스 테이블 삽입 및 삭제(정적 할당을 예로 들어)(샘플 코드에는 필요한 기본 기능이 포함되어 있음)

(4) 비트 순서로 검색, 값으로 검색

4. 연결리스트

(1).단일 연결 리스트

i. 단일 연결 리스트(리드 노드)의 정의

1. 기본 개념

선형 테이블:

(1).그것의 각 요소는,동일한 데이터 유형。

(2).요소들 사이,순서대로。

(3) 모두.헤더 요소그리고꼬리 요소。

(4).머리글과 바닥글을 제외하고 각 요소마다 하나씩 찾을 수 있습니다.직접적인 전구체그리고직계 후계자。

2. 선형 테이블의 기본 동작

테이블기스로부터

InitList(&L)：초기화선형 테이블

DestroyList(&L)：파괴하다

。

ListInsert(&L, i, e)：끼워 넣다, 테이블 L의 i번째 위치에 요소 e를 삽입합니다.

ListDelete(&L, i, &e)：삭제, 테이블 L의 i번째 요소를 삭제하고 e를 사용하여 삭제된 요소를 반환합니다.

。

LocateElem(L, e): 누르기값검색, 테이블에서 특정 키워드 e의 요소 찾기, 아래 첨자가 아닌 e의 순서 반환

GetElem(L, i): 누르기조금테이블의 i번째 요소 값을 검색하여 가져옵니다.

。

기타 일반 작업:

길이(L): 찾기테이블 리더경비

인쇄목록(L)：산출테이블모두요소

비어 있음(L): 판정 테이블비어있나요?, true 또는 false를 반환합니다.

판매 생성 및 추가, 삭제, 수정, 확인 등을 고도로 요약한 것입니다.

3. 서열표

~에 의해순차적 저장데이터의 선형 테이블

(1).정적 할당

  1. #define MAX 10
  2. //顺序表（静态分配）
  3. class SqList
  4. {
  5. public:
  6.     int data[MAX];
  7.     int length;
  8. };
  9. //初始化
  10. void InitList(SqList &l)
  11. {
  12.     for(int i = 0 ;i < 10 ;i++)
  13.     {
  14.         l.data[i] = 0;
  15.     }
  16.     l.length = 0;
  17. }
  18. //打印所有元素
  19. void PrintList(SqList &l)
  20. {
  21.     for (int i = 0; i < 10; i++)
  22.         cout << "第" << i << "个数：" << l.data[i] << endl;
  23. }
  24.  
  25. //测验
  26. void test01()
  27. {
  28.     SqList l;
  29.     InitList(l);
  30.     PrintList(l);
  31. }

(2).동적 할당

  1. #define InitSize 10
  2. //顺序表（动态分配）
  3. class SqList
  4. {
  5. public:
  6. 	int* data;		//指示动态分配数组的指针
  7. 	int MaxSize;	//指示最大容量
  8. 	int length;		//指示当前长度
  9. };
  10. //初始化顺序表
  11. void InitList(SqList& l)
  12. {
  13. 	l.data = new int[InitSize];
  14. 	l.MaxSize = InitSize;
  15. 	l.length = 0;
  16. 	for (int i = 0; i < l.MaxSize; i++)
  17. 	{
  18. 		l.data[i] = 0;
  19. 	}
  20. }
  21. //增长数组空间
  22. void IncreaseSize(SqList& l, int len)
  23. {
  24. 	int* p = l.data;					//暂存原数组中的数据
  25. 	l.data = new int[10 + len];			//扩展新的数组
  26. 	for (int i = 0; i < l.length; i++)	//将原数据拷贝进新数组中
  27. 	{
  28. 		l.data[i] = p[i];
  29. 	}
  30. 	l.MaxSize = InitSize + len;			//修改数组的状态数据
  31. 	delete p;							//将p释放
  32. }
  33. //打印所有元素
  34. void PrintList(SqList& l)
  35. {
  36. 	for (int i = 0; i < 10; i++)
  37. 		cout << "第" << i << "个数：" << l.data[i] << endl;
  38. }
  39.  
  40. void test01()
  41. {
  42. 	SqList l;
  43. 	InitList(l);
  44. 	PrintList(l);
  45. }

(3) 시퀀스 테이블 삽입 및 삭제(정적 할당을 예로 들어)(샘플 코드에는 필요한 기본 기능이 포함되어 있음)

//끼워 넣다

bool ListInsert(SqList&l, int d, int e)
{
if (l.length &gt;= MAX) //먼저 테이블이 꽉 찼는지, 삽입이 적법한지 확인합니다.
    {
cout &lt;&lt; "삽입에 실패했습니다. 상한선에 도달했습니다." &lt;&lt; endl;
거짓을 반환합니다.
    }
        
d &lt; 1 || d &gt; l.length + 1인 경우
    {
cout &lt;&lt; "삽입에 실패했습니다. 직속 선행자가 없습니다." &lt;&lt; endl;
거짓을 반환합니다.
    }
for (int j = l.length; j &gt;= d; j--) //삽입 지점 뒤의 요소를 뒤로 이동
l.데이터[j] = l.데이터[j - 1];
l.data[d - 1] = e; //삽입, d는 숫자를 참조하므로 배열 변환 시 1을 빼야 함
l.길이++;
참을 반환합니다.
}

//삭제
bool ListDelete(SqList& l, int d, int &e)
{
if (d &lt; 1 || d &gt;l.length) //삭제된 위치가 유효한지 확인
거짓을 반환합니다.
e = l.data[d - 1]; //삭제된 요소를 임시로 저장
for (int j = d; j &lt; l.length; j++) //삭제된 요소 뒤의 요소를 앞으로 이동합니다.
l.data[j - 1] = l.data[j]; //여기서 j = d여야 하며, j-1은 j에 의해 커버되고, j = d-1이면 다음 커버리지는 j가 커버됩니다. j+1이 커버되고 j+1은 결국 어레이의 최대 용량을 초과할 수 있습니다.
l.길이--;
참을 반환합니다.
}

샘플 코드

  1. #define MAX 10
  2. //顺序表（静态分配）
  3. class SqList
  4. {
  5. public:
  6.     int data[MAX];
  7.     int length;
  8. };
  9. //初始化
  10. void InitList(SqList& l)
  11. {
  12.     for (int i = 0; i < 10; i++)
  13.     {
  14.         l.data[i] = 0;
  15.     }
  16.     l.length = 0;
  17. }
  18. //打印所有元素
  19. void PrintList(SqList& l)
  20. {
  21.     for (int i = 0; i < 10; i++)
  22.         cout << "第" << i << "个数：" << l.data[i] << endl;
  23. }
  24. //存入数据
  25. void InputElem(SqList& l, int e)
  26. {
  27.     int i = 0;
  28.     while (i < MAX)
  29.     {
  30.         if (l.data[i] == 0)
  31.         {
  32.             l.data[i] = e;
  33.             l.length++;
  34.             break;
  35.         }
  36.         i++;
  37.     }
  38. }
  39. //获取顺序表长度
  40. int GetLength(SqList l)
  41. {
  42.     //cout << l.length << endl;
  43.     return l.length;
  44. }
  45. //插入
  46. bool ListInsert(SqList& l, int d, int e)
  47. {
  48.     if (l.length >= MAX)                        //首先要判断表是否已满、插入是否合法
  49.     {
  50.         cout << "插入失败，已达上限" << endl;
  51.         return false;
  52.     }
  53.         
  54.     if (d < 1 || d > l.length + 1)
  55.     {
  56.         cout << "插入失败,无直接前驱" << endl;
  57.         return false;
  58.     }
  59.     for (int j = l.length; j >= d; j--)         //将插入点之后的元素后移
  60.         l.data[j] = l.data[j - 1];
  61.     l.data[d - 1] = e;                          //插入，因为d指的是第几个数，在数组的换算中要减一
  62.     l.length++;
  63.     return true;
  64. }
  65. //删除
  66. bool ListDelete(SqList& l, int d, int &e)
  67. {
  68.     if (d < 1 || d >l.length)                   //判断删除的位置是否合法
  69.         return false;
  70.     e = l.data[d - 1];                          //暂存删除掉的元素
  71.     for (int j = d; j < l.length; j++)          //将被删除元素之后的元素前移
  72.         l.data[j - 1] = l.data[j];              //此处，必须是j = d，j-1被j覆盖，若j = d-1，则下文的覆盖会变为j 被j+1 覆盖，而j+1在最后有可能会超过数组的最大容量
  73.     l.length--;
  74.     return true;
  75. }
  76.  
  77. //查看情况
  78. void CheckList(SqList& l)
  79. {
  80.     PrintList(l);
  81.     cout << "当前长度为" << GetLength(l) << endl;
  82. }
  83.  
  84. //测验
  85. void test01()
  86. {
  87. 	SqList l;
  88. 	InitList(l);
  89.     
  90.     //输入部分数据
  91.     InputElem(l, 1);
  92.     InputElem(l, 2);
  93.     InputElem(l, 3);
  94.     InputElem(l, 4);
  95.     CheckList(l);
  96.  
  97.     //开始插入
  98.     if(ListInsert(l, 3, 6))
  99.         CheckList(l);
  100.  
  101.     //开始删除
  102.     int a = -1;
  103.     if (ListDelete(l, 2, a))
  104.         CheckList(l);
  105. }

(4) 비트 순서로 검색, 값으로 검색

매우 간단합니다. 자세히 설명할 필요가 없습니다.

  1. //判断d的合法性
  2. bool JugdeD(SqList l, int d)
  3. {
  4.     if (d < 1 || d > l.length)
  5.         return false;
  6.     return true;
  7. }
  8.  
  9. //按位序查找
  10. int GetElem(SqList l, int d)
  11. {
  12.     if (JugdeD(l, d))
  13.         return l.data[d - 1];
  14.     return 0;
  15. }
  16.  
  17. //按值查找
  18. int LocateElem(SqList l, int e)
  19. {
  20.     for (int i = 0; i < l.length; i++)
  21.     {
  22.         if (l.data[i] == e)       //数组储存的数据，若是类等复杂的数据类型，则需要对等号进行重载
  23.             return i + 1;
  24.     }
  25.     return 0;
  26. }
  27. //其余代码与上文相同
  28. //其中，JugdeD函数可以替换上文插入与删除中对位序合法性的判别————封装

4. 연결리스트

~에 의해체인 스토리지데이터의 선형 테이블

(1).단일 연결 리스트

i. 단일 연결 리스트(리드 노드)의 정의

  1. //单链表
  2. class LNode
  3. {
  4. public:
  5.     int data;           //数据域，存放数据
  6.     LNode* next;        //指针域，指向下一个节点
  7. };
  8. //用using关键字给类起别名，用LinkList指代的是头结点，代表的是整个链表
  9. using LinkList = LNode*;
  10.  
  11. //初始化
  12. bool InitList(LinkList& L)
  13. {
  14.     L = new LNode();
  15.     if (L == nullptr)   //如果成立，则说明内存不足，分配失败
  16.         return false;
  17.     L->next = nullptr;
  18.     return true;
  19. }

ii.삽입 및 삭제(선행 노드)

헤드 노드가 없으면 헤드 포인터의 변경에 주의하세요. 다른 모든 것은 동일합니다.

삽입(일반 버전)

  1. //插入
  2. bool ListInsert(LinkList& L, int i, int e)
  3. {
  4.     if (i < 1)                          //判断插入位点是否合法[1]——i值的合法性
  5.     {
  6.         cout << "i为负数" << endl;
  7.         return false;
  8.     }    
  9.     LNode* p = L;                       //让p与L指向相同的位点，L是指示头指针的，所以L是不能改变的
  10.     LNode* s = new LNode();             //新的数据储存
  11.     s->data = e;
  12.     while (p != nullptr && i != 1)      //由头结点起始，开始遍历寻找对应位点
  13.     {
  14.         p = p->next;
  15.         i--;
  16.     }
  17.     if (p == nullptr)                   //判断插入的位点是否合法[2]——i值对应的节点的合法性
  18.     {
  19.         cout << "插入位点超出实际长度" << endl;
  20.         return false;
  21.     }                     
  22.     s->next = p->next;                  //开始接轨，顺序不能乱
  23.     p->next = s;
  24.     return true;
  25. }

인서트(패키지 버전)

  1. //特定节点的后插操作
  2. bool InsertNextNode(LNode* p, int e)
  3. {
  4.     if (p == nullptr)                   
  5.     {
  6.         cout << "插入位点超出实际长度" << endl;
  7.         return false;
  8.     }
  9.     LNode* s = new LNode();
  10.     s->data = e;
  11.     s->next = p->next;
  12.     p->next = s;
  13.     return true;
  14. }
  15. //插入
  16. bool ListInsert(LinkList& L, int i, int e)
  17. {
  18.     if (i < 1)                          //判断插入位点是否合法[1]——i值的合法性
  19.     {
  20.         cout << "i为负数" << endl;
  21.         return false;
  22.     }    
  23.     LNode* p = L;                       //让p与L指向相同的位点，L是指示头指针的，所以L是不能改变的
  24.     while (p != nullptr && i != 1)      //由头结点起始，开始遍历寻找对应位点
  25.     {
  26.         p = p->next;
  27.         i--;
  28.     }
  29.     return InsertNextNode(p, e);        //被封装了的部分
  30. }

 

개인 프로필

그는 30년 이상 기술 연구에 전념해 왔으며, java, linux, javascript, php, css 등 다양한 언어에 능숙하며, 오픈 소스 분야에서 많은 공헌을 했습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.

내 연락처 정보

우편